結果

問題 No.1330 Multiply or Divide
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:45:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,364 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 81,740 KB
実行使用メモリ 105,152 KB
最終ジャッジ日時 2025-06-12 20:45:58
合計ジャッジ時間 5,492 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, M, P = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    max_r = -1
    best_e = 0
    for a in A:
        e = 0
        tmp = a
        while tmp % P == 0:
            e += 1
            tmp = tmp // P
        r = tmp
        if r > max_r:
            max_r = r
            best_e = e
    
    visited = set()
    queue = deque()
    queue.append( (1, 0) )
    
    while queue:
        x, ops = queue.popleft()
        if x > M:
            print(ops)
            return
        if x in visited:
            print(-1)
            return
        visited.add(x)
        
        if x % P == 0:
            k = 0
            tmp = x
            while tmp % P == 0:
                k += 1
                tmp = tmp // P
            x_final = tmp
            new_ops = ops + k
            if x_final > M:
                print(new_ops)
                return
            if x_final not in visited:
                queue.append( (x_final, new_ops) )
        else:
            x_new = x * max_r
            new_ops = ops + 1 + best_e
            if x_new > M:
                print(new_ops)
                return
            if x_new not in visited:
                queue.append( (x_new, new_ops) )
    
    print(-1)

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