結果
問題 | No.2365 Present of good number |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import collectionsfrom collections import defaultdictMOD = 10 ** 9 + 7def prime_factorize(n):a = []while n % 2 == 0:a.append(2)n //= 2f = 3while f * f <= n:if n % f == 0:a.append(f)n //= felse:f += 2if n != 1:a.append(n)return adef n_fact(N):c = collections.Counter(prime_factorize(N))return cN,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 * v2D = D2D[2] += 0D[3] += 0if D.keys() == {2,3}:breakK -= i + 1if K == 0:ans = 1for k,v in D.items():ans *= pow(k,v,MOD)ans %= MODprint(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 = A1X = X1K >>= 1ans = pow(2,A[0],MOD)ans *= pow(3,A[1],MOD)ans %= MODprint(ans)