結果
問題 |
No.1723 [Cherry 3rd Tune *] Dead on
|
ユーザー |
![]() |
提出日時 | 2021-11-04 23:25:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 1,532 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 80,256 KB |
最終ジャッジ日時 | 2024-10-15 05:59:07 |
合計ジャッジ時間 | 7,033 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#!/usr/bin/env python3 from pprint import pprint from sys import setrecursionlimit, stdin from typing import Dict, Iterable, Set INF: int = 1 << 62 setrecursionlimit(1_000_000) def inputs(type_=int): ins = input().split(' ') ins = [x for x in ins if x != ''] if isinstance(type_, Iterable): return [t(x) for t, x in zip(type_, ins)] else: return list(map(type_, ins)) def input_(type_=int): a, = inputs(type_) return a inputi = input_ def inputstr(): return input_(str) def answer(res) -> None: print(res) exit() # start coding def get_one_factor(n: int, start: int = 2) -> int: """ 一つの素因数を計算する 計算量は O(sqrt(n)) """ i = start while i * i <= n: if n % i == 0: return i i += 1 return n def compute_factors(n: int): """ 素因数分解を計算する 計算量は O(sqrt(n)log(n)) """ assert n >= 1 if n == 1: return {} d = {} start = 2 while n > 1: k = get_one_factor(n, start) start = k count = 0 while n % k == 0: n //= k count += 1 d[k] = count return d x, a, y, b = inputs() f1 = compute_factors(x) for k in f1: f1[k] *= a f2 = compute_factors(y) for k in f2: f2[k] *= b for k in set(f1) | set(f2): f1[k] = f1.get(k, 0) f2[k] = f2.get(k, 0) res = True for k in f2: res &= f1[k] >= f2[k] if res: print('Yes') else: print('No')