Submission #32508132

---

Source Code Expand

import random
import sys
input = sys.stdin.buffer.readline
U = (1 << 64) - 1


def prime_sieve(N):
    #sieve[i] : iの最小の素因数
    sieve = [0] * (N + 1)
    prime = []
    for i in range(2, N + 1):
        if sieve[i] == 0:
            sieve[i] = i
            prime.append(i)
        for p in prime:
            if p > sieve[i] or i * p > N:
                break
            sieve[i * p] = p
    return prime, sieve


def gen():
    a = random.randint(0, U - 1)
    b = random.randint(a + 1, U)
    while True:
        yield a
        yield b
        yield a ^ b


def gen_hash():
    a = random.randint(0, U-1)
    b = random.randint(a+1, U)
    value = [a, b, a ^ b]
    i = 0

    def inner():
        nonlocal i
        i += 1
        if i == 3:
            i = 0
        return value[i]
    return inner


def main(N, Q, A):
    Amax = max(A)
    prime, sieve = prime_sieve(Amax)

    F = {p: gen() for p in prime}
    xor = [0] * (N + 1)
    for i, a in enumerate(A, 1):
        while a > 1:
            p = sieve[a]
            xor[i] ^= next(F[p])
            a //= p
        xor[i] ^= xor[i-1]

    for _ in range(Q):
        L, R = map(int, input().split())
        if xor[R] ^ xor[L-1] == 0:
            print("Yes")
        else:
            print("No")


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

Submission Info

Judge Result