結果

問題 No.2972 確率的素数判定
ユーザー vwxyzvwxyz
提出日時 2024-11-29 21:52:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 400 ms / 2,000 ms
コード長 4,155 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 78,976 KB
最終ジャッジ日時 2024-11-29 21:52:21
合計ジャッジ時間 5,288 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 55 ms
65,920 KB
testcase_01 AC 53 ms
65,408 KB
testcase_02 AC 55 ms
65,408 KB
testcase_03 AC 54 ms
65,408 KB
testcase_04 AC 55 ms
66,176 KB
testcase_05 AC 56 ms
65,792 KB
testcase_06 AC 55 ms
65,280 KB
testcase_07 AC 55 ms
65,280 KB
testcase_08 AC 54 ms
65,792 KB
testcase_09 AC 56 ms
65,408 KB
testcase_10 AC 56 ms
65,536 KB
testcase_11 AC 55 ms
65,280 KB
testcase_12 AC 56 ms
65,664 KB
testcase_13 AC 57 ms
66,432 KB
testcase_14 AC 109 ms
74,752 KB
testcase_15 AC 132 ms
78,720 KB
testcase_16 AC 383 ms
78,976 KB
testcase_17 AC 396 ms
78,336 KB
testcase_18 AC 400 ms
78,876 KB
testcase_19 AC 392 ms
78,720 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class Prime:
def __init__(self,N):
assert N<=10**8
self.smallest_prime_factor=[None]*(N+1)
for i in range(2,N+1,2):
self.smallest_prime_factor[i]=2
n=int(N**.5)+1
for p in range(3,n,2):
if self.smallest_prime_factor[p]==None:
self.smallest_prime_factor[p]=p
for i in range(p**2,N+1,2*p):
if self.smallest_prime_factor[i]==None:
self.smallest_prime_factor[i]=p
for p in range(n,N+1):
if self.smallest_prime_factor[p]==None:
self.smallest_prime_factor[p]=p
self.primes=[p for p in range(N+1) if p==self.smallest_prime_factor[p]]
def Factorize(self,N):
assert N>=1
factors=defaultdict(int)
if N<=len(self.smallest_prime_factor)-1:
while N!=1:
factors[self.smallest_prime_factor[N]]+=1
N//=self.smallest_prime_factor[N]
else:
for p in self.primes:
while N%p==0:
N//=p
factors[p]+=1
if N<p*p:
if N!=1:
factors[N]+=1
break
if N<=len(self.smallest_prime_factor)-1:
while N!=1:
factors[self.smallest_prime_factor[N]]+=1
N//=self.smallest_prime_factor[N]
break
else:
if N!=1:
factors[N]+=1
return factors
def Divisors(self,N):
assert N>0
divisors=[1]
for p,e in self.Factorize(N).items():
pow_p=[1]
for _ in range(e):
pow_p.append(pow_p[-1]*p)
divisors=[i*j for i in divisors for j in pow_p]
return divisors
def Is_Prime(self,N):
return N==self.smallest_prime_factor[N]
def Totient(self,N):
for p in self.Factorize(N).keys():
N*=p-1
N//=p
return N
def Mebius(self,N):
fact=self.Factorize(N)
for e in fact.values():
if e>=2:
return 0
else:
if len(fact)%2==0:
return 1
else:
return -1
class Cumsum:
def __init__(self,lst,mod=0):
self.N=len(lst)
self.mod=mod
self.cumsum=[0]*(self.N+1)
self.cumsum[0]=0
for i in range(1,self.N+1):
self.cumsum[i]=self.cumsum[i-1]+lst[i-1]
if self.mod:
self.cumsum[i]%=self.mod
def __getitem__(self,i):
if type(i)==int:
if 0<=i<self.N:
a,b=i,i+1
elif -self.N<=i<0:
a,b=i+self.N,i+self.N+1
else:
raise IndexError('list index out of range')
else:
a,b=i.start,i.stop
if a==None or a<-self.N:
a=0
elif self.N<=a:
a=self.N
elif a<0:
a+=self.N
if b==None or self.N<=b:
b=self.N
elif b<-self.N:
b=0
elif b<0:
b+=self.N
s=self.cumsum[b]-self.cumsum[a]
if self.mod:
s%=self.mod
return s
def __setitem__(self,i,x):
if -self.N<=i<0:
i+=self.N
elif not 0<=i<self.N:
raise IndexError('list index out of range')
self.cumsum[i+1]=self.cumsum[i]+x
if self.mod:
self.cumsum[i+1]%=self.mod
def __len__(self):
return self.N
def __str__(self):
lst=[self.cumsum[i+1]-self.cumsum[i] for i in range(self.N)]
if self.mod:
for i in range(self.N):
lst[i]%=self.mod
return "["+", ".join(map(str,lst))+"]"
def __repr__(self):
return "Cumsum("+str(self)+")"
M=10**5
P=Prime(10**5)
C=[0]*(M+1)
for p in P.primes:
C[p]+=1
C=Cumsum(C)
T=int(input())
for t in range(T):
N,P,Q=map(int,input().split())
c=C[:N+1]
ans=c*P/(c*P+(N-c)*(100-Q))
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0