結果
問題 | No.1164 GCD Products hard |
ユーザー |
👑 ![]() |
提出日時 | 2021-06-15 03:50:03 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 996 bytes |
コンパイル時間 | 253 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 319,360 KB |
最終ジャッジ日時 | 2024-12-25 17:30:38 |
合計ジャッジ時間 | 38,767 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 TLE * 8 |
ソースコード
def Sieve_of_Eratosthenes(N,mode=False):"""Nまでのエラトステネスの篩を実行N:自然数mode:False->素数のリスト,True->素数かどうかのリスト(False->[2,3,5,...],True->[0,0,1,1,0,1,...])"""if N==0:return [0]T=[1]*(N+1)T[0]=T[1]=0for x in range(4,N+1,2): T[x]=0for x in range(9,N+1,3): T[x]=0a=5Flag=0while a*a<=N:if T[a]:b=a*ac=2*awhile b<=N:T[b]=0b+=ca+=2+2*FlagFlag^=1if mode:return Telse:return [k for k in range(N+1) if T[k]]#==================================================A,B,N=map(int,input().split())P=Sieve_of_Eratosthenes(B,False)X=1Mod=10**9+7for p in P:q=pwhile True:if q>B: breakc=B//q-(A-1)//qif c==0: continued=pow(c,N,Mod-1)X*=pow(p,d,Mod)X%=Modq*=pprint(X)