結果

問題 No.2365 Present of good number
ユーザー ntudantuda
提出日時 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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0