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

• 問題: No.854 公平なりんご分配
• ユーザー: vwxyz
• 提出日時: 2024-04-08 07:30:34
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 2,628 ms / 3,153 ms
• コード長: 3,269 bytes
• コンパイル時間: 1,866 ms
• コンパイル使用メモリ: 81,444 KB
• 実行使用メモリ: 260,440 KB
• 最終ジャッジ日時: 2024-04-08 08:04:42
• 合計ジャッジ時間: 49,871 ms
• ジャッジサーバーID （参考情報）: judge12 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	36 ms; 53,716 KB
testcase_01	AC	36 ms; 53,460 KB
testcase_02	AC	36 ms; 53,716 KB
testcase_03	AC	35 ms; 53,716 KB
testcase_04	AC	37 ms; 53,716 KB
testcase_05	AC	37 ms; 53,716 KB
testcase_06	AC	38 ms; 53,716 KB
testcase_07	AC	37 ms; 53,716 KB
testcase_08	AC	40 ms; 53,716 KB
testcase_09	AC	37 ms; 53,716 KB
testcase_10	AC	36 ms; 53,716 KB
testcase_11	AC	46 ms; 53,716 KB
testcase_12	AC	48 ms; 59,720 KB
testcase_13	AC	46 ms; 59,720 KB
testcase_14	AC	38 ms; 53,716 KB
testcase_15	AC	39 ms; 53,716 KB
testcase_16	AC	42 ms; 59,720 KB
testcase_17	AC	51 ms; 59,720 KB
testcase_18	AC	45 ms; 59,720 KB
testcase_19	AC	44 ms; 59,720 KB
testcase_20	AC	43 ms; 59,720 KB
testcase_21	AC	42 ms; 59,720 KB
testcase_22	AC	92 ms; 72,876 KB
testcase_23	AC	74 ms; 70,800 KB
testcase_24	AC	96 ms; 75,920 KB
testcase_25	AC	67 ms; 68,728 KB
testcase_26	AC	93 ms; 75,932 KB
testcase_27	AC	81 ms; 72,880 KB
testcase_28	AC	80 ms; 72,876 KB
testcase_29	AC	70 ms; 66,664 KB
testcase_30	AC	69 ms; 68,720 KB
testcase_31	AC	96 ms; 76,336 KB
testcase_32	AC	374 ms; 127,964 KB
testcase_33	AC	362 ms; 77,808 KB
testcase_34	AC	559 ms; 147,444 KB
testcase_35	AC	465 ms; 113,628 KB
testcase_36	AC	291 ms; 77,728 KB
testcase_37	AC	307 ms; 124,632 KB
testcase_38	AC	248 ms; 77,680 KB
testcase_39	AC	656 ms; 153,844 KB
testcase_40	AC	298 ms; 77,808 KB
testcase_41	AC	360 ms; 114,044 KB
testcase_42	AC	503 ms; 123,888 KB
testcase_43	AC	528 ms; 124,984 KB
testcase_44	AC	564 ms; 141,992 KB
testcase_45	AC	424 ms; 81,168 KB
testcase_46	AC	604 ms; 142,464 KB
testcase_47	AC	289 ms; 77,840 KB
testcase_48	AC	496 ms; 145,132 KB
testcase_49	AC	412 ms; 114,544 KB
testcase_50	AC	374 ms; 124,552 KB
testcase_51	AC	584 ms; 145,528 KB
testcase_52	AC	499 ms; 80,468 KB
testcase_53	AC	313 ms; 77,932 KB
testcase_54	AC	538 ms; 80,560 KB
testcase_55	AC	231 ms; 77,632 KB
testcase_56	AC	237 ms; 77,632 KB
testcase_57	AC	347 ms; 77,944 KB
testcase_58	AC	509 ms; 81,308 KB
testcase_59	AC	235 ms; 77,424 KB
testcase_60	AC	417 ms; 78,716 KB
testcase_61	AC	270 ms; 77,728 KB
testcase_62	AC	392 ms; 79,144 KB
testcase_63	AC	313 ms; 78,996 KB
testcase_64	AC	217 ms; 77,472 KB
testcase_65	AC	413 ms; 117,900 KB
testcase_66	AC	364 ms; 78,152 KB
testcase_67	AC	452 ms; 79,296 KB
testcase_68	AC	411 ms; 80,492 KB
testcase_69	AC	377 ms; 151,440 KB
testcase_70	AC	233 ms; 77,724 KB
testcase_71	AC	256 ms; 77,692 KB
testcase_72	AC	408 ms; 78,668 KB
testcase_73	AC	369 ms; 125,656 KB
testcase_74	AC	634 ms; 138,148 KB
testcase_75	AC	365 ms; 77,940 KB
testcase_76	AC	438 ms; 124,860 KB
testcase_77	AC	445 ms; 145,436 KB
testcase_78	AC	576 ms; 81,152 KB
testcase_79	AC	520 ms; 79,924 KB
testcase_80	AC	528 ms; 120,984 KB
testcase_81	AC	369 ms; 121,756 KB
testcase_82	AC	1,377 ms; 260,056 KB
testcase_83	AC	2,104 ms; 245,344 KB
testcase_84	AC	1,969 ms; 260,180 KB
testcase_85	AC	1,139 ms; 224,700 KB
testcase_86	AC	191 ms; 89,892 KB
testcase_87	AC	1,171 ms; 260,436 KB
testcase_88	AC	1,167 ms; 260,436 KB
testcase_89	AC	1,441 ms; 260,432 KB
testcase_90	AC	1,406 ms; 260,436 KB
testcase_91	AC	1,206 ms; 260,440 KB
testcase_92	AC	2,628 ms; 259,800 KB
testcase_93	AC	1,889 ms; 223,060 KB

ソースコード

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")