これは、公式解説の \(2\) 枚目です。議論の流れは \(1\) 枚目と全く同じですが、異なるハッシュの設計法について説明します。

この問題は、「与えれる区間ごとに、全ての素因数が \(3\) の倍数個含まれるか」というある意味集合の比較のような問題です。この手の問題には、ハッシュが有効です。
\(3\) の倍数個含まれるかどうかの判定をしたいので、 \(3\) つかけると元に戻るような操作を使ってハッシュを設計したいです。そのような方法はいくつか考えられますが、そのうち \(1\) つを紹介します。

まず、長さ \(N\) のマス目を用意し、\(i\) 番目のマス目には、\(A_i\) の素因数を好きな順番で並べておきます。たとえば問題文中のサンプルケースでは

| 7 | 7, 7 | 2, 3, 5 | | 3, 5 | 2, 2, 2 | 2, 3 | 2, 5 |

のようになります。次に、各素数 \(p\) について \(0\) 以上 \(2\) 以下の整数の乱数 \(a_p\) を選んでおきます。これらは独立に、それぞれ一様分布で選びます。

上で並べられた素因数に対し、ハッシュ値を以下のように定めます。

• 素数 \(p\) のハッシュ値を \(a_p\) とする

さらに、区間に対するハッシュを、その区間内の素因数に割り当てられたすべてのハッシュの和 \(\pmod 3\) として定めます。このようにハッシュを設計すると、「 \(A_{L_i} \times A_{L_i+1} \times \dots A_{R_i}\) が立方数である」 \(\Rightarrow\) 「 その区間のハッシュが \(0\) となる」が成立します。

立方数でないときはどうなるでしょうか？一般に、立方数でないときのハッシュは一個以上の一様独立な乱数の和 \(\pmod 3\) となり、これが \(0\) となる確率はちょうど \(\frac{1}{3}\) であることが示せます。「 \(A_{L_i} \times A_{L_i+1} \times \dots A_{R_i}\) が立方数である」 \(\Rightarrow\) 「 その区間のハッシュが \(0\) となる確率が \(\frac{1}{3}\)」が成立します。

そこで、この判定を \(B=50\) 回繰り返し、ハッシュ値がつねに \(0\) であれば立方数、一回でも \(0\) 以外になれば立方数でないと答えることにしましょう。この解法では、立方数であるケースでは確実に立方数であると答えられるものの、立方数でないにもかかわらず立方数であると答えてしまう可能性が低い確率 (\(\frac{1}{3^{50}}\)) で存在します。

では、ここからはこの解法が正答できる確率に話題を移しましょう。 上で見たように、一つのクエリの判定に失敗する確率は高々 \(\frac{1}{3^{50}}\) です。これを \(Q\) 回行うので、テストケース数が仮に \(T=100\) ケースだったとすると、全てのテストケースを実行する間に一回以上失敗する確率は高々 \(\frac{1}{3^{50}} \cdot QT \leq 10^{-16}\) となり、十分低確率となります。

計算量は、判定の実行回数を \(B\) 、 \(A\) の最大値を \(M=10^6\) として、最初に \(1\) 以上 \(M\) 以下の整数についてまとめて素因数分解を行うと \(O((BN+M) \log M + BQ)\) です。

なお、公式解説の \(1\) 枚目では質の良いメルセンヌ・ツイスタを乱数生成に利用していましたが、こちらではより高速なXorshiftを利用しています。

実装例(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;
}