結果

問題 No.1250 汝は倍数なりや?
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:56:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 99 ms / 1,000 ms
コード長 907 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 107,644 KB
最終ジャッジ日時 2025-03-20 18:58:04
合計ジャッジ時間 4,267 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def get_prime_factors(h):
    factors = {}
    while h % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        h = h // 2
    i = 3
    while i * i <= h:
        while h % i == 0:
            factors[i] = factors.get(i, 0) + 1
            h = h // i
        i += 2
    if h > 1:
        factors[h] = 1
    return factors

n, h = map(int, input().split())
a_list = list(map(int, input().split()))

if h == 1:
    print("YES")
    exit()

if any(x == 0 for x in a_list):
    print("YES")
    exit()

factors = get_prime_factors(h)

flag = True
for p, required in factors.items():
    total = 0
    for a in a_list:
        current = abs(a)
        cnt = 0
        while current % p == 0:
            cnt += 1
            current = current // p
        total += cnt
        if total >= required:
            break
    if total < required:
        flag = False
        break

print("YES" if flag else "NO")
0