結果

問題 No.28 末尾最適化
ユーザー KudeKude
提出日時 2020-09-04 18:47:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,218 ms / 5,000 ms
コード長 1,022 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 87,108 KB
実行使用メモリ 149,484 KB
最終ジャッジ日時 2023-08-17 13:39:33
合計ジャッジ時間 4,161 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 83 ms
76,636 KB
testcase_01 AC 3,218 ms
149,484 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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)
    ps, cnts = fact[b]
    xp = []
    for xi in x:
        d = []
        for p in ps:
            cnt = 0
            while xi % p == 0:
                cnt += 1
                xi //= p
            d.append(cnt)
        xp.append(tuple(d))
    ans = 10 ** 9
    for i in range(len(ps)):
        xp.sort(key=lambda x: x[i])
        d = [0] * len(ps)
        for xpcnts in xp[:k]:
            for j, cnt in enumerate(xpcnts):
                d[j] += cnt
        t = min(di // ci for di, ci in zip(d, cnts))
        ans = min(ans, t)
    print(ans)
0