結果

問題 No.854 公平なりんご分配
ユーザー ああいい
提出日時 2022-03-04 19:05:34
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,299 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 82,012 KB
実行使用メモリ 329,048 KB
最終ジャッジ日時 2024-07-18 16:08:50
合計ジャッジ時間 37,150 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 80 MLE * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
rr = sys.stdin

N = int(rr.readline())
A = list(map(int,rr.readline().split()))
prime = []
dat = [0] * (2 * 10 ** 3)
for i in range(2,2 * 10 ** 3):
    if dat[i] == 0:
        prime.append(i)
        for j in range(2 * i,2 * 10 ** 3,i):
            dat[j] = 1
n = len(prime)
_sum = [[0] * n for _ in range(N+1)]

bit = [0] * (N + 1)
def add(i,x):
    while i <= N:
        bit[i] += x
        i += i & -i
def fold(i):
    ans = 0
    while i > 0:
        ans += bit[i]
        i -= i & -i
    return ans

for i in range(N):
    if A[i] == 0:
        add(i+1,1)
        for j in range(n):
            _sum[i+1][j] = _sum[i][j]
        continue
    for j in range(n):
        p = prime[j]
        count = 0
        while A[i] % p == 0:
            count += 1
            A[i] //= p
        _sum[i+1][j] = _sum[i][j] + count
Q = int(rr.readline())
for _ in range(Q):
    P,l,r = map(int,rr.readline().split())
    if fold(r) - fold(l-1) > 0:
        print('Yes')
        continue
    flag = True
    for j in range(n):
        p = prime[j]
        count = 0
        while P % p == 0:
            count += 1
            P //= p
        if count > _sum[r][j] - _sum[l-1][j]:
            flag = False
            break
    if flag and P == 1:
        print('Yes')
    else:
        print('NO')
0