提出 #31642741

---

ソースコード 拡げる

import sys
from random import randrange
input = sys.stdin.readline
MAX = 10 ** 6

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

# ランダムな整数を割り当てる
table = [[0] * (MAX + 1)] * 3
table[1] = [randrange(1 << 60) for _ in range(MAX + 1)]
table[2] = [randrange(1 << 60) for _ in range(MAX + 1)]

# 線形ふるい
primes = []
min_factor = [0] * (MAX + 1)
for i in range(2, MAX + 1):
    if min_factor[i] == 0:
        primes.append(i)
        min_factor[i] = i
    f = min_factor[i]
    for p in primes:
        j = i * p
        if p > f or j > MAX:
            break
        min_factor[j] = p

# ハッシュを計算
B = [0]
cnt = [0] * (MAX + 1) # 素数の出てきた回数
h = 0

def add(p: int): # 素数を追加
    global h
    h ^= table[cnt[p]][p]
    cnt[p] += 1
    if cnt[p] == 3:
        cnt[p] = 0
    h ^= table[cnt[p]][p]

for a in A:
    while a > 1:
        p = min_factor[a]
        add(p)
        a //= p
    B.append(h)

# クエリを処理
for _ in range(Q):
    L, R = map(int, input().split())
    print("Yes" if B[L - 1] == B[R] else "No")

提出情報

ジャッジ結果