Subtask 1

When coding a naive solution for the problem, we simply multiply all of the numbers from a given range ~l~ to ~r~, before checking if it is a perfect square. However, the product of these numbers will quickly overflow the integer data type so it is not enough to pass the first subtask. To solve the first subtask, the storage of numbers must be condensed.

Let ~P~ be the product of the numbers in a query which has the prime factors, ~f_1, f_2 ... f_m~.

We observe that if all the prime factors of ~P~ are raised to an even power then it is a perfect square. This is because ~P~ can be represented as a square of ~f_1^{(k_1/2)} \cdot f_2^{(k_2/2)} ... f_m^{(k_m/2)}~ where ~k_i~ is the exponent to which that prime factor is raised. Following this idea, we convert the numbers on each card into their prime factorizations. One possible algorithm for prime factorization is the Sieve of Eratosthenes.

To complete a query, we add up the powers for a given prime factor and check that it is even. If every prime factor passes this check, then we can output yes

Subtask 2

For the second subtask, we notice that only the parity of ~f_1, f_2 ... f_m~ is relevant. Thus each prime factor can be represented by two states, ~0~ for an even exponent and ~1~ for an odd exponent. Every number can then be represented as a collection of ~1~s and ~0~s, a bitset. For example, ~84~ can be represented as ~2^2 \cdot 3^1 \cdot 5^0 \cdot 7^1~ or ~0101~. In order to combine the parity of two sets of prime factors, we must perform the XOR operation on their bitsets.

Now that we have the prime factors represented as bits, we can combine the parity of two sets of prime factors in ~O(1)~, however, each query still takes ~O(n)~ time.

Our next observation is that XOR is a commutative operation and as such we can create a Prefix XOR Array (PXA). Similar to the Prefix Sum Array (PSA) which stores the sum of all numbers up the current index, the PXA will store the XORs of all numbers up to the current index.

Recall that the sum of numbers between ~l~ and ~r~ in a PSA is

~PSA[r] = PSA[l-1]~

Similarly, to find the XORs of numbers between ~l~ and ~r~ we write

~PXA[r] \oplus PXA[l-1]~

Using this optimization, queries can be answered in ~O(1)~ time.