結果

問題 No.854 公平なりんご分配
ユーザー titia
提出日時 2024-11-15 08:39:17
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,874 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 319,812 KB
最終ジャッジ日時 2024-11-15 08:39:46
合計ジャッジ時間 26,984 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 80 MLE * 12
権限があれば一括ダウンロードができます

ソースコード

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