#970673 (PyPy3) No.854 公平なりんご分配

提出ソース

結果

問題	No.854 公平なりんご分配
ユーザー	vwxyz
提出日時	2024-04-08 07:30:34
言語	PyPy3 (7.3.15)
結果	AC
実行時間	2,078 ms / 3,153 ms
コード長	3,269 bytes
コンパイル時間	384 ms
コンパイル使用メモリ	82,468 KB
実行使用メモリ	260,544 KB
最終ジャッジ日時	2024-10-01 04:59:01
合計ジャッジ時間	39,245 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	39 ms 52,480 KB
testcase_01	AC	39 ms 52,480 KB
testcase_02	AC	41 ms 53,120 KB
testcase_03	AC	39 ms 52,608 KB
testcase_04	AC	39 ms 52,992 KB
testcase_05	AC	39 ms 52,864 KB
testcase_06	AC	41 ms 53,120 KB
testcase_07	AC	39 ms 52,864 KB
testcase_08	AC	39 ms 52,736 KB
testcase_09	AC	40 ms 52,608 KB
testcase_10	AC	39 ms 52,480 KB
testcase_11	AC	41 ms 52,864 KB
testcase_12	AC	46 ms 59,520 KB
testcase_13	AC	47 ms 59,520 KB
testcase_14	AC	42 ms 53,376 KB
testcase_15	AC	43 ms 53,248 KB
testcase_16	AC	47 ms 59,648 KB
testcase_17	AC	47 ms 59,520 KB
testcase_18	AC	49 ms 59,264 KB
testcase_19	AC	46 ms 59,392 KB
testcase_20	AC	46 ms 59,392 KB
testcase_21	AC	47 ms 59,648 KB
testcase_22	AC	85 ms 72,832 KB
testcase_23	AC	73 ms 69,632 KB
testcase_24	AC	97 ms 76,416 KB
testcase_25	AC	67 ms 67,968 KB
testcase_26	AC	94 ms 76,892 KB
testcase_27	AC	81 ms 71,936 KB
testcase_28	AC	80 ms 72,704 KB
testcase_29	AC	64 ms 66,432 KB
testcase_30	AC	70 ms 68,608 KB
testcase_31	AC	97 ms 76,768 KB
testcase_32	AC	321 ms 128,384 KB
testcase_33	AC	308 ms 78,736 KB
testcase_34	AC	522 ms 147,840 KB
testcase_35	AC	426 ms 114,008 KB
testcase_36	AC	263 ms 78,080 KB
testcase_37	AC	299 ms 125,312 KB
testcase_38	AC	229 ms 78,184 KB
testcase_39	AC	592 ms 154,240 KB
testcase_40	AC	270 ms 78,556 KB
testcase_41	AC	342 ms 116,408 KB
testcase_42	AC	467 ms 124,160 KB
testcase_43	AC	485 ms 125,440 KB
testcase_44	AC	523 ms 142,464 KB
testcase_45	AC	382 ms 82,016 KB
testcase_46	AC	530 ms 143,104 KB
testcase_47	AC	266 ms 78,256 KB
testcase_48	AC	463 ms 145,612 KB
testcase_49	AC	380 ms 114,816 KB
testcase_50	AC	326 ms 124,928 KB
testcase_51	AC	541 ms 146,144 KB
testcase_52	AC	473 ms 81,004 KB
testcase_53	AC	287 ms 78,468 KB
testcase_54	AC	479 ms 81,024 KB
testcase_55	AC	221 ms 77,924 KB
testcase_56	AC	225 ms 78,420 KB
testcase_57	AC	307 ms 78,212 KB
testcase_58	AC	477 ms 81,920 KB
testcase_59	AC	223 ms 77,824 KB
testcase_60	AC	380 ms 78,976 KB
testcase_61	AC	250 ms 78,168 KB
testcase_62	AC	355 ms 79,488 KB
testcase_63	AC	292 ms 79,232 KB
testcase_64	AC	205 ms 77,824 KB
testcase_65	AC	381 ms 118,400 KB
testcase_66	AC	312 ms 78,540 KB
testcase_67	AC	410 ms 80,076 KB
testcase_68	AC	377 ms 81,280 KB
testcase_69	AC	383 ms 152,556 KB
testcase_70	AC	220 ms 78,004 KB
testcase_71	AC	225 ms 78,228 KB
testcase_72	AC	368 ms 79,224 KB
testcase_73	AC	347 ms 125,952 KB
testcase_74	AC	587 ms 138,936 KB
testcase_75	AC	310 ms 78,524 KB
testcase_76	AC	410 ms 125,464 KB
testcase_77	AC	434 ms 145,852 KB
testcase_78	AC	521 ms 81,664 KB
testcase_79	AC	490 ms 80,404 KB
testcase_80	AC	492 ms 121,728 KB
testcase_81	AC	372 ms 122,416 KB
testcase_82	AC	1,209 ms 260,092 KB
testcase_83	AC	1,839 ms 245,500 KB
testcase_84	AC	1,710 ms 260,352 KB
testcase_85	AC	1,033 ms 225,476 KB
testcase_86	AC	160 ms 90,368 KB
testcase_87	AC	1,046 ms 260,484 KB
testcase_88	AC	1,067 ms 260,544 KB
testcase_89	AC	1,244 ms 260,212 KB
testcase_90	AC	1,222 ms 260,224 KB
testcase_91	AC	1,046 ms 259,824 KB
testcase_92	AC	2,078 ms 259,504 KB
testcase_93	AC	1,642 ms 209,532 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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)
Q=int(input())
ans_lst=["Yes"]*Q
P,L,R=[],[],[]
for q in range(Q):
    p,l,r=map(int,input().split())
    l-=1
    P.append(p)
    L.append(l)
    R.append(r)
cumsum0=[0]*(N+1)
for i in range(N):
    if A[i]==0:
        cumsum0[i+1]=1
for i in range(1,N+1):
    cumsum0[i]+=cumsum0[i-1]
for p in Pr.primes:
    cumsum=[0]*(N+1)
    for i in range(N):
        if A[i]:
            while A[i]%p==0:
                cumsum[i+1]+=1
                A[i]//=p
    for i in range(1,N+1):
        cumsum[i]+=cumsum[i-1]
    for q in range(Q):
        if cumsum0[R[q]]-cumsum0[L[q]]:
            continue
        cnt=0
        while P[q]%p==0:
            P[q]//=p
            cnt+=1
        if cumsum[R[q]]-cumsum[L[q]]<cnt:
            ans_lst[q]="NO"
for q in range(Q):
    if cumsum0[R[q]]-cumsum0[L[q]]:
        continue
    if P[q]>=2:
        ans_lst[q]="NO"
print(*ans_lst,sep="\n")

yukicoder

結果

テストケース

ソースコード