結果
問題 | No.2365 Present of good number |
ユーザー |
|
提出日時 | 2023-06-30 22:37:27 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,706 bytes |
コンパイル時間 | 148 ms |
コンパイル使用メモリ | 82,036 KB |
実行使用メモリ | 67,080 KB |
最終ジャッジ日時 | 2024-07-07 10:28:15 |
合計ジャッジ時間 | 3,398 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 WA * 8 |
ソースコード
from collections import defaultdictIsPrime = [True for _ in range(10**5 + 1)]IsPrime[0] = IsPrime[1] = FalsePrimes = []for i in range(2, 10**5 + 1):if IsPrime[i]:Primes.append(i)for j in range(i * i, 10**5 + 1, i):IsPrime[j] = Falsen, k = map(int, input().split())mod = 10**9 + 7P = defaultdict(int)seen = set()for prime in Primes:while n % prime == 0:seen.add(prime)P[prime] += 1n //= primeC = [(p, c) for p, c in P.items()]while not (len(seen) <= 2 and (2 in seen or 3 in seen)) and k > 0:k -= 1P = defaultdict(int)seen = set()for p, c in C:p += 1if IsPrime[p]:seen.add(p)P[p] += cP[p] %= mod - 1else:for prime in Primes:while p % prime == 0:seen.add(prime)P[prime] += cP[prime] %= mod - 1p //= primeif p == 1:breakC = [(p, c) for p, c in P.items()]if k > 0:q, r = divmod(k, 2)P = defaultdict(int)for p, c in C:if p == 2:if r == 0:P[2] += c * pow(2, q, mod - 1)P[2] %= mod - 1else:P[3] += c * pow(2, q, mod - 1)P[3] %= mod - 1else:if r == 0:P[3] += c * pow(2, q, mod - 1)P[3] %= mod - 1else:P[2] += c * pow(2, q + 1, mod - 1)P[2] %= mod - 1C = [(p, c) for p, c in P.items()]ans = 1for p, c in C:ans *= pow(p, c, mod)ans %= modprint(ans)