結果

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

ソースコード

diff # 

import math

def main():
    import sys
    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]))
    
    t_list = []
    b_list = []
    for a in A:
        t = 0
        while a % P == 0:
            a = a // P
            t +=1
        t_list.append(t)
        b_list.append(a)
    
    has_t0 = False
    max_b_t0 = 0
    for i in range(N):
        if t_list[i] == 0:
            has_t0 = True
            if b_list[i] > max_b_t0:
                max_b_t0 = b_list[i]
    
    if has_t0:
        if max_b_t0 <= 1:
            print(-1)
            return
        else:
            if 1 > M:
                print(0)
                return
            else:
                logM = math.log(M)
                logb = math.log(max_b_t0)
                k = (logM // logb) + 1
                if max_b_t0 ** k > M:
                    print(k)
                else:
                    print(k + 1)
                return
    else:
        max_efficiency = -float('inf')
        best_b = 0
        best_t = 0
        for i in range(N):
            if b_list[i] <= 1:
                continue
            t = t_list[i]
            efficiency = math.log(b_list[i]) / (1 + t)
            if efficiency > max_efficiency or (efficiency == max_efficiency and b_list[i] > best_b):
                max_efficiency = efficiency
                best_b = b_list[i]
                best_t = t
        
        if best_b == 0 or best_b <= 1:
            print(-1)
            return
        else:
            if 1 > M:
                print(0)
                return
            else:
                logM = math.log(M)
                logb = math.log(best_b)
                k = (logM // logb) + 1
                total_ops = k * (1 + best_t)
                print(total_ops)
                return

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