結果
| 問題 | No.1164 GCD Products hard |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2021-06-15 03:53:18 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 997 bytes |
| コンパイル時間 | 201 ms |
| コンパイル使用メモリ | 82,548 KB |
| 実行使用メモリ | 160,256 KB |
| 最終ジャッジ日時 | 2024-06-07 13:31:51 |
| 合計ジャッジ時間 | 7,256 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 580 ms
149,964 KB |
| testcase_01 | AC | 755 ms
160,256 KB |
| testcase_02 | AC | 558 ms
136,576 KB |
| testcase_03 | AC | 199 ms
87,424 KB |
| testcase_04 | TLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
ソースコード
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]=0
for x in range(4,N+1,2): T[x]=0
for x in range(9,N+1,3): T[x]=0
a=5
Flag=0
while a*a<=N:
if T[a]:
b=a*a
c=2*a
while b<=N:
T[b]=0
b+=c
a+=2+2*Flag
Flag^=1
if mode:
return T
else:
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=1
Mod=10**9+7
for p in P:
q=p
t=0
while True:
if q>B: break
c=B//q-(A-1)//q
if c==0: continue
t+=pow(c,N,Mod-1)
q*=p
X*=pow(p,t,Mod)
X%=Mod
print(X)