結果

問題 No.2365 Present of good number
ユーザー ntuda
提出日時 2023-07-01 16:34:28
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,342 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 594,348 KB
最終ジャッジ日時 2024-07-08 02:40:27
合計ジャッジ時間 4,257 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other MLE * 1 -- * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

import collections
from collections import defaultdict
MOD = 10 ** 9 + 7
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def n_fact(N):
    c = collections.Counter(prime_factorize(N))
    return c

N,K = map(int,input().split())
D = n_fact(N)

for i in range(K):
    D2 = defaultdict(int)
    for k,v in D.items():
        DT = n_fact(k+1)
        for k2, v2 in DT.items():
            D2[k2] += v * v2
    D = D2
    D[2] += 0
    D[3] += 0
    if D.keys() == {2,3}:
        break
K -= i + 1
if K == 0:
    ans = 1
    for k,v in D.items():
        ans *= pow(k,v,MOD)
    ans %= MOD
    print(ans)
    exit()

A = [D[2],D[3]]
X = [[0,2],[1,0]]
A1 = [0,0]
X1 = [[0,0],[0,0]]

while K > 0:
    if K & 1:
        A1[0] = X[0][0] * A[0] + X[0][1] * A[1]
        A1[1] = X[1][0] * A[0] + X[1][1] * A[1]
    X1[0][0] = X[0][0] * X[0][0] + X[0][1] * X[1][0]
    X1[1][0] = X[1][0] * X[0][0] + X[1][1] * X[1][0]
    X1[0][1] = X[0][0] * X[0][1] + X[0][1] * X[1][1]
    X1[1][1] = X[1][0] * X[0][1] + X[1][1] * X[1][1]
    A = A1
    X = X1
    K >>= 1

ans = pow(2,A[0],MOD)
ans *= pow(3,A[1],MOD)
ans %= MOD
print(ans)
0