結果
問題 | No.2365 Present of good number |
ユーザー |
![]() |
提出日時 | 2023-06-30 21:55:52 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,107 bytes |
コンパイル時間 | 336 ms |
コンパイル使用メモリ | 82,448 KB |
実行使用メモリ | 56,492 KB |
最終ジャッジ日時 | 2024-07-07 09:38:18 |
合計ジャッジ時間 | 2,915 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 11 WA * 28 |
ソースコード
from collections import * def factorization(n): arr = [] temp = n for i in range(2, int(-(-n**0.5//1))+1): if temp%i==0: cnt=0 while temp%i==0: cnt+=1 temp //= i arr.append([i, cnt]) if temp!=1: arr.append([temp, 1]) return arr N, K = map(int, input().split()) mod = 10**9 + 7 ans = 1 D = defaultdict(int) for i, cnt in factorization(N): D[i] += cnt while K: new = defaultdict(int) if len(D) == 1: if 2 in D or 3 in D: break if len(D) == 2: if 2 in D and 3 in D: break K -= 1 for k, v in D.items(): for i, cnt in factorization(k + 1): new[i] += cnt new, D = D, new if K == 0: ans = 1 for k, v in D.items(): ans *= pow(k, v, mod) ans %= mod print(ans) else: m = K//2 K %= 2 D[2] = D[2] * pow(2, m, mod - 1) D[3] = D[3] * pow(2, m, mod - 1) if K: D[2], D[3] = D[3] * 2, D[2] ans = pow(2, D[2], mod) * pow(3, D[3], mod) % mod print(ans)