This is the second page of the official editorials.

We explained one of the ways to design the hash function. We will explain another here. The flow of discussion is the same as the first page.

In the official editorial, we said that “we want to design an operation that applying three times is equivalent to identity operation”; one of the most straightforward example would be an addition on \(\mod 3\). So we will design a hash based on the addition on \(\mod 3\).

First, initialize a sequence of (unsigned) integers \(H=(H_0,H_1,\dots,H_N)\) of length \(N+1\) with \(0\).

Then, for each prime factor (denoting by \(p\)), do the following operation.

• First, choose a random value \(X\) as an integer between \(0\) and \(2\) (inclusive) for each prime factor \(p\).
• Then, for each integer \(i\) from \(1\) through \(N\), if \(A_i\) has \(k\) prime factors \(p\), then update as \(H_i \leftarrow H_i + k \times X\).

By designing the hash by the procedure above, it holds that “the number of each prime factor in the segment \([l, r]\) is a multiple of \(3\)” \(\Rightarrow\) “\(H_l + H_{l+1} + \dots + H_r \equiv 0 \mod 3\)”. (Note that the converse does not always hold.)

After performing the operation above for all prime factors \(p\), let \(H'\) be the array of cumulative sum, so that \(H'_i=(H_0 + H_1 + \dots + H_i) \mod 3\).
Then, for each query, it holds that “\(A_{L_i} \times A_{L_i+1} \times \dots A_{R_i}\) is a cubic number” \(\Rightarrow\) “\(H'_{L_i-1} \equiv H'_{R_i} \mod 3\).” (Again, the converse does not hold)
The contraposition does hold: “\(H'_{L_i-1} \not\equiv H'_{R_i} \mod 3\)” \(\Rightarrow\) “\(A_{L_i} \times A_{L_i+1} \times \dots A_{R_i}\) is not a cubic number”.

Therefore, we can tell the following facts:

• the misjudgment of type “\(A_{L_i} \times A_{L_i+1} \times \dots A_{R_i}\) is a cubic number but \(H'_{L_i-1} \not\equiv H'_{R_i} \mod 3\)” will never happen
• however, the misjudgment of type “\(A_{L_i} \times A_{L_i+1} \times \dots A_{R_i}\) is not a cubic number but \(H'_{L_i-1} \equiv H'_{R_i} \mod 3\)” may happen

We can define the probability \(P\) as the probability of “misjudging \(H'_{L_i-1} \equiv H'_{R_i} \mod 3\) while \(A_{L_i} \times A_{L_i+1} \times \dots A_{R_i}\) is not a cubic number.”
Suppose that we have a program that repeats this judgement \(B\) times. If the misjudgment happens in all trials for a single query, then the answer will be considered wrong.
Then, the probability of being accepted for this problem is \((1-P^B)^{QT}\), where \(B\) bit is the size of hash value and \(T\) is the number of test cases.

Let’s make a rough estimate on \(B=50,P=1/3,T=100\) (for each trial, the both hand sides of the equivalent relation has the value of either \(0,1,2 \mod 3\), so we can roughly estimate as \(P=1/3\)). Then, the probability of being accepted is \((1-(1/3)^{50})^{2 \times 10^7} > 0.9999999999999999\), which is high enough.
Let’s make a little more pessimistic estimate. Let \(B=50,P=0.5,T=200\). Then, the probability of being accepted is \((1-0.5^{50})^{4 \times 10^7} >0.9999999\); this is still a high probability.
If you are still worried, you may repeat the operation multiple times to increase the value of \(B\). Just making the value \(B\) a little larger result in a drastic increase on the probability of being accepted.

The time complexity is \(O((BN+M) \log M + BQ)\), where \(B\) is the number of trials and \(M=10^6\) is the maximum value of \(A\), assuming that the prime factorization of integers between \(1\) and \(M\) are done at once beforehand.

Note that in the first page of the editorial we used Mersenne twister as a high-quality random number generator, but this time we use rather faster xorshift.

Sample code (C++):

#include<bits/stdc++.h>
#define MAX 1000005

using namespace std;

unsigned long long xor64(){
  static unsigned long long x=88172645463325252LL;
  x^=(x<<13);
  x^=(x>>7);
  return (x^=(x<<17));
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,q;
  cin >> n >> q;
  vector<int> a(n);
  for(auto &nx : a){cin >> nx;}
  vector<int> l(q),r(q);
  for(int i=0;i<q;i++){cin >> l[i] >> r[i];}

  vector<vector<int>> pf(MAX);
  for(int i=2;i<MAX;i++){
    if(!pf[i].empty()){continue;}
    for(int j=i;j<MAX;j+=i){
      int mj=j;
      while(mj%i==0){
        pf[j].push_back(i);
        mj/=i;
      }
    }
  }
  vector<bool> res(q,true);
  for(int tr=0;tr<50;tr++){
    vector<int> mem(MAX,0);
    for(int i=0;i<MAX;i++){mem[i]=xor64()%3;}
    vector<int> h(n+1,0);
    for(int i=0;i<n;i++){
      for(auto &nx : pf[a[i]]){
        h[i+1]+=mem[nx];
      }
    }
    for(int i=1;i<=n;i++){h[i]+=h[i-1];}
    for(int i=0;i<q;i++){
      if((h[r[i]]-h[l[i]-1])%3){res[i]=false;}
    }
  }
  for(int i=0;i<q;i++){
    if(res[i]){cout << "Yes\n";}
    else{cout << "No\n";}
  }
  return 0;
}