結果
問題 |
No.2751 429-like Number
|
ユーザー |
![]() |
提出日時 | 2024-07-01 21:49:09 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,901 ms / 4,000 ms |
コード長 | 1,737 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-07-01 21:49:30 |
合計ジャッジ時間 | 20,421 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 22 |
ソースコード
import math from collections import defaultdict def Miller_Rabin_Primality_Test(N): if N==1: return False NN=N-1 NN=NN//(NN&-NN) if N<4759123141: lst=[2,7,61] elif N<341550071728321: lst=[2,3,5,7,11,13,17] else: lst=[2,3,5,7,11,13,17,19,23,29,31,37] if N in lst: return True for a in lst: n=NN p=pow(a,n,N) if p==1: continue while p!=N-1: p=p*p%N if p==1 or n==N-1: return False n<<=1 return True def Pollard_Rho(N): if N==1: return None if Miller_Rabin_Primality_Test(N): return None m=1<<N.bit_length()//8 for c in range(1,99): f=lambda x:(x**2+c)%N y,r,q,g=2,1,1,1 while g==1: x=y for _ in range(r): y=f(y) k=0 while k<r and g==1: ys=y for _ in range(min(m,r-k)): y=f(y) q=q*abs(x-y)%N g=math.gcd(q,N) k+=m r<<=1 if g==N: g=1 while g==1: ys=f(ys) g=math.gcd(abs(x-ys),N) if g<N: return g def Factorize_Pollard_Rho(N): stack=[N] factorize=defaultdict(int) while stack: x=stack.pop() p=Pollard_Rho(x) if p==None: factorize[x]+=1 continue stack.append(p) stack.append(x//p) return factorize Q=int(input()) for q in range(Q): A=int(input()) F=Factorize_Pollard_Rho(A) if sum(F.values())==3: ans="Yes" else: ans="No" print(ans)