結果

問題 No.854 公平なりんご分配
ユーザー titiatitia
提出日時 2024-11-15 08:36:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,873 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 81,996 KB
実行使用メモリ 319,792 KB
最終ジャッジ日時 2024-11-15 08:37:16
合計ジャッジ時間 26,396 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
62,096 KB
testcase_01 AC 48 ms
61,388 KB
testcase_02 AC 48 ms
62,072 KB
testcase_03 AC 53 ms
61,680 KB
testcase_04 AC 48 ms
61,104 KB
testcase_05 AC 47 ms
62,028 KB
testcase_06 AC 48 ms
60,556 KB
testcase_07 AC 48 ms
61,428 KB
testcase_08 AC 49 ms
62,284 KB
testcase_09 AC 48 ms
63,016 KB
testcase_10 AC 47 ms
61,380 KB
testcase_11 AC 49 ms
62,132 KB
testcase_12 AC 49 ms
63,576 KB
testcase_13 AC 49 ms
62,368 KB
testcase_14 AC 48 ms
61,872 KB
testcase_15 AC 48 ms
62,232 KB
testcase_16 AC 49 ms
63,600 KB
testcase_17 AC 49 ms
62,504 KB
testcase_18 AC 48 ms
61,088 KB
testcase_19 AC 50 ms
63,084 KB
testcase_20 AC 47 ms
61,040 KB
testcase_21 AC 51 ms
62,708 KB
testcase_22 AC 98 ms
77,632 KB
testcase_23 AC 86 ms
78,408 KB
testcase_24 AC 99 ms
78,736 KB
testcase_25 AC 72 ms
73,484 KB
testcase_26 AC 105 ms
79,456 KB
testcase_27 AC 92 ms
78,636 KB
testcase_28 AC 87 ms
76,836 KB
testcase_29 AC 60 ms
67,672 KB
testcase_30 AC 71 ms
73,256 KB
testcase_31 AC 104 ms
78,632 KB
testcase_32 AC 193 ms
127,960 KB
testcase_33 AC 219 ms
104,460 KB
testcase_34 AC 296 ms
148,292 KB
testcase_35 AC 240 ms
132,908 KB
testcase_36 AC 210 ms
80,620 KB
testcase_37 AC 192 ms
124,648 KB
testcase_38 AC 171 ms
115,732 KB
testcase_39 AC 430 ms
152,880 KB
testcase_40 AC 236 ms
100,332 KB
testcase_41 AC 246 ms
121,120 KB
testcase_42 AC 273 ms
147,348 KB
testcase_43 AC 330 ms
123,712 KB
testcase_44 AC 329 ms
141,852 KB
testcase_45 AC 362 ms
89,572 KB
testcase_46 AC 416 ms
140,720 KB
testcase_47 AC 219 ms
111,892 KB
testcase_48 AC 255 ms
146,244 KB
testcase_49 AC 247 ms
147,632 KB
testcase_50 AC 175 ms
124,704 KB
testcase_51 AC 403 ms
144,012 KB
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 WA -
testcase_63 WA -
testcase_64 WA -
testcase_65 WA -
testcase_66 WA -
testcase_67 WA -
testcase_68 WA -
testcase_69 WA -
testcase_70 WA -
testcase_71 WA -
testcase_72 WA -
testcase_73 WA -
testcase_74 WA -
testcase_75 WA -
testcase_76 WA -
testcase_77 WA -
testcase_78 WA -
testcase_79 WA -
testcase_80 WA -
testcase_81 WA -
testcase_82 MLE -
testcase_83 MLE -
testcase_84 MLE -
testcase_85 MLE -
testcase_86 MLE -
testcase_87 MLE -
testcase_88 MLE -
testcase_89 MLE -
testcase_90 MLE -
testcase_91 MLE -
testcase_92 MLE -
testcase_93 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
input = sys.stdin.readline

class Bit_indexed_tree():
    def __init__(self, LEN):
        self.BIT = [0]*(LEN+1) # 1-indexedなtree. 配列BITの長さはLEN+1にしていることに注意。
        self.LEN = LEN

    def update(self,v,w): # index vにwを加える
        while v<=self.LEN:
            self.BIT[v]+=w
            v+=(v&(-v)) # v&(-v)で、最も下の立っているビット. 自分を含む大きなノードへ. たとえばv=3→v=4

    def getvalue(self,v): # [1,v]の区間の和を求める
        ANS=0
        while v!=0:
            ANS+=self.BIT[v]
            v-=(v&(-v)) # 自分より小さい自分の和を構成するノードへ. たとえばv=14→v=12へ
        return ANS

    def bisect_on_BIT(self,x): # [1,ind]の和がはじめてx以上になるindexを探す

        if x<=0:
            return 0
        
        ANS=0
        h=1<<((self.LEN).bit_length()-1) # LEN以下の最小の2ベキ
        while h>0:
            if ANS+h<=self.LEN and self.BIT[ANS+h]<x:
                x-=self.BIT[ANS+h]
                ANS+=h
            h//=2

        return ANS+1 # LENまでの和がx未満のとき, LEN+1を返すことに注意


# 線形篩。エラトステネスの篩を線形にできる。

MAX=2010
Sieve=[-1]*MAX
Primes=[]

for i in range(2,MAX):
    if Sieve[i]==-1:
        Primes.append(i)
        Sieve[i]=i

    for p in Primes:
        if p*i>=MAX or p>Sieve[i]:
            break
        else:
            Sieve[p*i]=p


# 素因数分解
def fact(x):
    D=dict()
    while x!=1:
        k=Sieve[x]
        if k in D:
            D[k]+=1
        else:
            D[k]=1
        x//=k
    return D

# 約数列挙
def faclist(x):
    LIST=[1]
    while x!=1:
        k=Sieve[x]
        count=0
        while x%k==0:
            count+=1
            x//=k

        LIST2=[]
        for l in LIST:
            for i in range(1,count+1):
                LIST2.append(l*k**i)
        LIST+=LIST2

    return LIST

N=int(input())
A=list(map(int,input().split()))

D=[-1]*2030
for i in range(len(Primes)):
    D[Primes[i]]=i

LIST=[Bit_indexed_tree(N+10) for i in range(305)]

for i in range(N):
    if A[i]==0:
        LIST[304].update(i+2,1)
        continue
    F=fact(A[i])

    for f in F:
        LIST[D[f]].update(i+2,F[f])

Q=int(input())

for tests in range(Q):
    p,l,r=map(int,input().split())

    k=LIST[304].getvalue(r-1+2)-LIST[304].getvalue(l-2+2)
    if k>0:
        print("NO")
        continue
    if p==1:
        print("Yes")
        continue

    for i in range(304):
        if p%Primes[i]==0:
            k=LIST[i].getvalue(r-1+2)-LIST[i].getvalue(l-2+2)

            for tt in range(k):
                if p%Primes[i]==0:
                    p//=Primes[i]
                else:
                    break

    if p==1:
        print("Yes")
    else:
        print("NO")
0