結果

問題 No.28 末尾最適化
コンテスト
ユーザー titia
提出日時 2021-11-18 06:03:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,187 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,720 KB
実行使用メモリ 102,656 KB
最終ジャッジ日時 2024-12-24 22:18:11
合計ジャッジ時間 4,334 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from operator import itemgetter
from math import gcd

LIST=[[], [], [2], [3], [2], [5], [2, 3], [7], [2], [3], [2, 5], [11], [2, 3], [13], [2, 7], [3, 5], [2], [17], [2, 3], [19], [2, 5], [3, 7], [2, 11], [23], [2, 3], [5], [2, 13], [3], [2, 7], [29], [2, 3, 5], [31], [2], [3, 11], [2, 17], [5, 7], [2, 3], [37], [2, 19], [3, 13]]
VALUE=[[], [], [1], [1], [2], [1], [1, 1], [1], [3], [2], [1, 1], [1], [2, 1], [1], [1, 1], [1, 1], [4], [1], [1, 2], [1], [2, 1], [1, 1], [1, 1], [1], [3, 1], [2], [1, 1], [3], [2, 1], [1], [1, 1, 1], [1], [5], [1, 1], [1, 1], [1, 1], [2, 2], [1], [1, 1], [1, 1]]

def calc(NOW,x):
    A=0
    while NOW%x==0:
        NOW//=x
        A+=1
    return A
    
Q=int(input())
for tests in range(Q):
    seed,N,K,B=map(int,input().split())

    NOW=seed
    X=[gcd(seed,B)]

    for i in range(N):
        NOW=1+(NOW*NOW+NOW*12345)%100000009
        X.append(gcd(NOW,B))

    ANS=1<<30

    for i in range(len(LIST[B])):
        f=LIST[B][i]
        X.sort(key=lambda x:calc(x,f))

        AX=0
        for j in range(K):
            AX+=calc(X[j],f)
        ANS=min(ANS,AX//VALUE[B][i])
            
    print(ANS)
0