結果

問題 No.854 公平なりんご分配
ユーザー H3PO4
提出日時 2025-06-07 07:39:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,337 ms / 3,153 ms
コード長 1,680 bytes
コンパイル時間 1,164 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 297,540 KB
最終ジャッジ日時 2025-06-07 07:40:40
合計ジャッジ時間 38,866 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from array import array

input = sys.stdin.buffer.readline


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return (i for i in range(n + 1) if is_prime[i])


def main():
    N = int(input())
    A = array("I", map(int, input().split()))
    Q = int(input())
    queries = [(map(int, input().split())) for _ in range(Q)]

    MAX = max(max(A), 1)
    P = array("I", primes(MAX))
    L = len(P)
    acc_list = [array("I", [0] * (N + 1)) for _ in range(L)]

    INF = 10**7
    for i, a in enumerate(A, 1):
        if a:
            temp = a
            for x, pr in enumerate(P):
                ct = 0
                while not temp % pr:
                    temp //= pr
                    ct += 1
                acc_list[x][i] = ct
        else:
            for p in range(L):
                acc_list[p][i] = INF
    for p in range(L):
        for i in range(N):
            acc_list[p][i + 1] += acc_list[p][i]

    def solve(p, l, r):
        temp = p
        for x, pr in enumerate(P):
            if pr > temp:
                break
            ct = 0
            while not temp % pr:
                temp //= pr
                ct += 1
            diff = acc_list[x][r] - acc_list[x][l - 1]
            if diff >= INF:
                return True
            elif diff < ct:
                return False
        return temp == 1

    for p, l, r in queries:
        print("Yes" if solve(p, l, r) else "NO")


if __name__ == "__main__":
    main()
0