結果
問題 | No.2365 Present of good number |
ユーザー |
![]() |
提出日時 | 2023-06-30 22:36:11 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,430 bytes |
コンパイル時間 | 94 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-07-07 10:27:14 |
合計ジャッジ時間 | 1,984 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 7 WA * 32 |
ソースコード
class PrimeNumbers:def __init__(self,nmax):from math import isqrtrootnmax = isqrt(nmax)self.prime_judgement = [True]*(rootnmax+1)self.prime_judgement[0] = self.prime_judgement[1] = Falsefor i in range(2,rootnmax+1):if self.prime_judgement[i]:for j in range(2,rootnmax//i+1):self.prime_judgement[i*j] = Falseself.prime_list = []for i,flag in enumerate(self.prime_judgement):if flag: self.prime_list.append(i)def prime_factorization(self,n):return_list = []for i in self.prime_list:if n==1 or i*i>n: breakif n%i==0:return_list.append([i,0])while n%i==0: return_list[-1][1] += 1; n //= iif n!=1: return_list.append([n,1])return return_listfrom collections import defaultdictn,k = map(int,input().split())mod = 10**9+7pn = PrimeNumbers(2*n)c = {k:v for k,v in pn.prime_factorization(n)}for i in range(k):d = defaultdict(int)for p,q in c.items():for x,y in pn.prime_factorization(p+1): d[x] += y*qc = d; ans = 1if (k-i)%2==0 or set(c.keys())-{2,3}: continueif 2 in c: ans *= (pow(2,c[2]*pow(2,(k-i)//2,mod),mod))if 3 in c: ans *= (pow(3,c[2]*pow(2,(k-i)//2,mod),mod))exit(print(ans%mod))ans = 1for p,q in c.items(): ans *= pow(p,q,mod)print(ans%mod)