結果

問題 No.28 末尾最適化
コンテスト
ユーザー Kude
提出日時 2020-09-04 19:04:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 907 ms / 5,000 ms
コード長 725 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 82,176 KB
最終ジャッジ日時 2024-11-26 11:02:40
合計ジャッジ時間 1,836 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

fact = [0,1]
for b in range(2, 37):
    ps = []
    for p in range(2, 32):
        cnt = 0
        while b % p == 0:
            cnt += 1
            b //= p
        if cnt:
            ps.append((p, cnt))
    fact.append(ps)

for _ in range(int(input())):
    seed, n, k, b = map(int, input().split())
    x = [seed]
    now = seed
    for i in range(n):
        now = 1 + (now * (now + 12345)) % 100000009
        x.append(now)
    ans = 10 ** 9
    for p, cntb in fact[b]:
        cntx = []
        for xi in x:
            cnt = 0
            while xi % p == 0:
                cnt += 1
                xi //= p
            cntx.append(cnt)
        cntx.sort()
        ans = min(ans, sum(cntx[:k]) // cntb)
    print(ans)
0