結果

問題 No.1330 Multiply or Divide
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:27:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,502 bytes
コンパイル時間 275 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 122,588 KB
最終ジャッジ日時 2025-06-12 15:28:04
合計ジャッジ時間 5,623 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 38 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def compute_a_b(num, p):
    a = 0
    while num % p == 0:
        a += 1
        num = num // p
    return a, num

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    P = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    
    group1 = []
    group2 = []
    
    for num in A:
        if num == 0:
            continue
        a, b = compute_a_b(num, P)
        if a == 0:
            if b > 1:
                group1.append(b)
        else:
            group2.append((a, b))
    
    if len(group1) > 0:
        max_b = max(group1)
        t = 0
        current = 1
        while current <= M:
            current *= max_b
            t += 1
        print(t)
    else:
        if not group2:
            print(-1)
            return
        max_rate = -1
        selected_a = 0
        selected_b = 0
        for a, b in group2:
            if b <= 1:
                continue
            rate = b ** (1.0 / (1 + a))
            if rate > max_rate:
                max_rate = rate
                selected_a = a
                selected_b = b
        if selected_b == 0 or selected_b == 1:
            print(-1)
        else:
            t = 0
            current = 1
            while current <= M:
                current *= selected_b
                t += 1
            total_steps = t * (1 + selected_a)
            print(total_steps)

if __name__ == '__main__':
    main()
0