結果

問題 No.2365 Present of good number
ユーザー ntudantuda
提出日時 2023-07-01 16:34:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,342 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 86,948 KB
実行使用メモリ 88,300 KB
最終ジャッジ日時 2023-09-22 10:47:22
合計ジャッジ時間 5,110 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
76,348 KB
testcase_01 AC 99 ms
71,704 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
権限があれば一括ダウンロードができます

ソースコード

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