結果
| 問題 | No.854 公平なりんご分配 |
| ユーザー |
 vwxyz
|
| 提出日時 | 2024-04-08 07:11:40 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 3,154 bytes |
| コンパイル時間 | 376 ms |
| コンパイル使用メモリ | 82,048 KB |
| 実行使用メモリ | 322,300 KB |
| 最終ジャッジ日時 | 2024-10-01 04:56:13 |
| 合計ジャッジ時間 | 48,864 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 39 ms
58,624 KB |
| testcase_01 | AC | 39 ms
52,608 KB |
| testcase_02 | AC | 38 ms
52,864 KB |
| testcase_03 | AC | 38 ms
52,864 KB |
| testcase_04 | AC | 39 ms
52,736 KB |
| testcase_05 | AC | 40 ms
52,868 KB |
| testcase_06 | AC | 38 ms
52,864 KB |
| testcase_07 | AC | 38 ms
53,120 KB |
| testcase_08 | AC | 38 ms
53,376 KB |
| testcase_09 | AC | 39 ms
52,992 KB |
| testcase_10 | AC | 38 ms
52,992 KB |
| testcase_11 | AC | 37 ms
52,864 KB |
| testcase_12 | AC | 44 ms
59,904 KB |
| testcase_13 | AC | 42 ms
59,648 KB |
| testcase_14 | AC | 38 ms
53,376 KB |
| testcase_15 | AC | 38 ms
53,120 KB |
| testcase_16 | AC | 44 ms
60,032 KB |
| testcase_17 | AC | 45 ms
59,648 KB |
| testcase_18 | AC | 43 ms
59,520 KB |
| testcase_19 | AC | 44 ms
59,648 KB |
| testcase_20 | AC | 43 ms
59,648 KB |
| testcase_21 | AC | 44 ms
59,648 KB |
| testcase_22 | AC | 90 ms
73,984 KB |
| testcase_23 | AC | 85 ms
72,320 KB |
| testcase_24 | AC | 111 ms
79,360 KB |
| testcase_25 | AC | 82 ms
73,472 KB |
| testcase_26 | AC | 114 ms
79,564 KB |
| testcase_27 | AC | 99 ms
79,360 KB |
| testcase_28 | AC | 101 ms
77,992 KB |
| testcase_29 | AC | 66 ms
66,560 KB |
| testcase_30 | AC | 80 ms
71,424 KB |
| testcase_31 | AC | 108 ms
79,100 KB |
| testcase_32 | AC | 379 ms
128,248 KB |
| testcase_33 | AC | 478 ms
104,992 KB |
| testcase_34 | AC | 804 ms
148,480 KB |
| testcase_35 | AC | 601 ms
133,000 KB |
| testcase_36 | AC | 275 ms
80,644 KB |
| testcase_37 | AC | 373 ms
125,248 KB |
| testcase_38 | AC | 307 ms
115,736 KB |
| testcase_39 | AC | 1,215 ms
152,116 KB |
| testcase_40 | AC | 547 ms
101,376 KB |
| testcase_41 | AC | 585 ms
121,264 KB |
| testcase_42 | AC | 833 ms
147,328 KB |
| testcase_43 | AC | 991 ms
123,280 KB |
| testcase_44 | AC | 902 ms
141,760 KB |
| testcase_45 | AC | 665 ms
90,084 KB |
| testcase_46 | AC | 1,176 ms
141,184 KB |
| testcase_47 | AC | 484 ms
112,264 KB |
| testcase_48 | AC | 668 ms
146,464 KB |
| testcase_49 | AC | 573 ms
147,792 KB |
| testcase_50 | AC | 377 ms
124,652 KB |
| testcase_51 | AC | 1,322 ms
144,672 KB |
| testcase_52 | AC | 662 ms
106,112 KB |
| testcase_53 | AC | 379 ms
105,600 KB |
| testcase_54 | AC | 633 ms
111,812 KB |
| testcase_55 | AC | 282 ms
105,856 KB |
| testcase_56 | AC | 275 ms
107,684 KB |
| testcase_57 | AC | 415 ms
102,232 KB |
| testcase_58 | AC | 627 ms
87,924 KB |
| testcase_59 | AC | 288 ms
99,056 KB |
| testcase_60 | AC | 520 ms
102,216 KB |
| testcase_61 | AC | 218 ms
82,456 KB |
| testcase_62 | AC | 504 ms
97,700 KB |
| testcase_63 | AC | 354 ms
99,272 KB |
| testcase_64 | AC | 254 ms
86,632 KB |
| testcase_65 | AC | 483 ms
139,100 KB |
| testcase_66 | AC | 352 ms
93,184 KB |
| testcase_67 | AC | 515 ms
116,464 KB |
| testcase_68 | AC | 501 ms
94,464 KB |
| testcase_69 | AC | 401 ms
153,628 KB |
| testcase_70 | AC | 275 ms
101,088 KB |
| testcase_71 | AC | 279 ms
103,168 KB |
| testcase_72 | AC | 372 ms
81,432 KB |
| testcase_73 | AC | 374 ms
126,276 KB |
| testcase_74 | AC | 644 ms
137,228 KB |
| testcase_75 | AC | 446 ms
104,260 KB |
| testcase_76 | AC | 435 ms
123,868 KB |
| testcase_77 | AC | 484 ms
145,888 KB |
| testcase_78 | AC | 671 ms
96,244 KB |
| testcase_79 | AC | 680 ms
118,116 KB |
| testcase_80 | AC | 608 ms
120,196 KB |
| testcase_81 | AC | 413 ms
121,900 KB |
| testcase_82 | MLE | - |
| testcase_83 | MLE | - |
| testcase_84 | MLE | - |
| testcase_85 | AC | 1,203 ms
227,328 KB |
| testcase_86 | AC | 270 ms
89,592 KB |
| testcase_87 | MLE | - |
| testcase_88 | MLE | - |
| testcase_89 | MLE | - |
| testcase_90 | MLE | - |
| testcase_91 | MLE | - |
| testcase_92 | MLE | - |
| testcase_93 | -- | - |
ソースコード
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
N=int(input())
A=list(map(int,input().split()))
max_A=max(A)
Pr=Prime(max_A)
cumsum=[None]*(max_A+1)
for p in Pr.primes:
cumsum[p]=[0]*(N+1)
for i in range(N):
if A[i]:
while A[i]%p==0:
cumsum[p][i+1]+=1
A[i]//=p
for i in range(1,N+1):
cumsum[p][i]+=cumsum[p][i-1]
cumsum[0]=[0]*(N+1)
for i in range(N):
if A[i]==0:
cumsum[0][i+1]=1
for i in range(1,N+1):
cumsum[0][i]+=cumsum[0][i-1]
Q=int(input())
for q in range(Q):
P,L,R=map(int,input().split())
L-=1
ans="Yes"
if cumsum[0][R]-cumsum[0][L]==0:
for p in Pr.primes:
cnt=0
while P%p==0:
P//=p
cnt+=1
if cumsum[p][R]-cumsum[p][L]<cnt:
ans="NO"
if P>=2:
ans="NO"
print(ans)