結果
問題 | No.2972 確率的素数判定 |
ユーザー | vwxyz |
提出日時 | 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 |
ソースコード
class Prime:def __init__(self,N):assert N<=10**8self.smallest_prime_factor=[None]*(N+1)for i in range(2,N+1,2):self.smallest_prime_factor[i]=2n=int(N**.5)+1for p in range(3,n,2):if self.smallest_prime_factor[p]==None:self.smallest_prime_factor[p]=pfor i in range(p**2,N+1,2*p):if self.smallest_prime_factor[i]==None:self.smallest_prime_factor[i]=pfor p in range(n,N+1):if self.smallest_prime_factor[p]==None:self.smallest_prime_factor[p]=pself.primes=[p for p in range(N+1) if p==self.smallest_prime_factor[p]]def Factorize(self,N):assert N>=1factors=defaultdict(int)if N<=len(self.smallest_prime_factor)-1:while N!=1:factors[self.smallest_prime_factor[N]]+=1N//=self.smallest_prime_factor[N]else:for p in self.primes:while N%p==0:N//=pfactors[p]+=1if N<p*p:if N!=1:factors[N]+=1breakif N<=len(self.smallest_prime_factor)-1:while N!=1:factors[self.smallest_prime_factor[N]]+=1N//=self.smallest_prime_factor[N]breakelse:if N!=1:factors[N]+=1return factorsdef Divisors(self,N):assert N>0divisors=[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 divisorsdef Is_Prime(self,N):return N==self.smallest_prime_factor[N]def Totient(self,N):for p in self.Factorize(N).keys():N*=p-1N//=preturn Ndef Mebius(self,N):fact=self.Factorize(N)for e in fact.values():if e>=2:return 0else:if len(fact)%2==0:return 1else:return -1class Cumsum:def __init__(self,lst,mod=0):self.N=len(lst)self.mod=modself.cumsum=[0]*(self.N+1)self.cumsum[0]=0for i in range(1,self.N+1):self.cumsum[i]=self.cumsum[i-1]+lst[i-1]if self.mod:self.cumsum[i]%=self.moddef __getitem__(self,i):if type(i)==int:if 0<=i<self.N:a,b=i,i+1elif -self.N<=i<0:a,b=i+self.N,i+self.N+1else:raise IndexError('list index out of range')else:a,b=i.start,i.stopif a==None or a<-self.N:a=0elif self.N<=a:a=self.Nelif a<0:a+=self.Nif b==None or self.N<=b:b=self.Nelif b<-self.N:b=0elif b<0:b+=self.Ns=self.cumsum[b]-self.cumsum[a]if self.mod:s%=self.modreturn sdef __setitem__(self,i,x):if -self.N<=i<0:i+=self.Nelif not 0<=i<self.N:raise IndexError('list index out of range')self.cumsum[i+1]=self.cumsum[i]+xif self.mod:self.cumsum[i+1]%=self.moddef __len__(self):return self.Ndef __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.modreturn "["+", ".join(map(str,lst))+"]"def __repr__(self):return "Cumsum("+str(self)+")"M=10**5P=Prime(10**5)C=[0]*(M+1)for p in P.primes:C[p]+=1C=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)