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

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

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

のようになります。次に、各素数 \(p\) について \(64\) bit の符号なし整数の乱数 \(a_p, b_p\) を選んでおきます。これらは独立に、それぞれ一様分布で選びます。

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

• 各素数 \(p\) について、現れる \(p\) の左から順にハッシュ値を \(a_p, b_p, a_p \oplus b_p, a_p, b_p, a_p \oplus b_p, ...\) とする (\(a \oplus b\) で \(a\) と \(b\) のbitごとの XOR)

上の例では

| \(a_7\) | \(b_7\), \(a_7 \oplus b_7\) | \(a_2\), \(a_3\), \(a_5\) | | \(b_3\), \(b_5\) | \(b_2\), \(a_2 \oplus b_2\), \(a_2\) | \(b_2\), \(a_3 \oplus b_3\) | \(a_2 \oplus b_2\), \(a_5 \oplus b_5\) |

となります。

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

立方数でないときはどうなるでしょうか？たとえば、サンプルで二番目のクエリに対応するハッシュは \(a_2 \oplus a_3 \oplus a_5 \oplus a_7\) となります。一般に、立方数でないときのハッシュは一個以上の一様独立な乱数の XOR となり、これが \(0\) となる確率はちょうど \(\frac{1}{2^{64}}\) であることが示せます。「 \(A_{L_i} \times A_{L_i+1} \times \dots A_{R_i}\) が立方数である」 \(\Rightarrow\) 「 その区間のハッシュが \(0\) となる確率が \(\frac{1}{2^{64}}\)」が成立します。

そこで、ハッシュ値が \(0\) であれば立方数、そうでなければ立方数でないと答えることにしましょう。この解法では、立方数であるケースでは確実に立方数であると答えられるものの、立方数でないにもかかわらず立方数であると答えてしまう可能性が低い確率で存在します。

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

今回の場合はすでに十分低確率なので不要ですが、これでも不安な場合は判定を複数回行うなどすると正答できる確率を上昇させられます。(上の解法も、確率 \(\frac{1}{2}\) で失敗する方法を \(64\) 回繰り返したと見ることもできます。)

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

実装例(C++):

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

using namespace std;

int main(){
  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];}
  
  uint_fast64_t seed=202202052100238523;
  mt19937_64 engine(seed);
  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);
  vector<vector<uint_fast64_t>> hs(MAX,vector<uint_fast64_t>(3,0));
  for(int i=0;i<MAX;i++){
    hs[i][0]=engine();
    hs[i][1]=engine();
    hs[i][2]=(hs[i][0]^hs[i][1]);
  }
  vector<int> bk(MAX,0);
  vector<uint_fast64_t> rw(n+1,0);
  for(int i=0;i<n;i++){
    rw[i+1]=rw[i];
    for(auto &nx : pf[a[i]]){
      rw[i+1]^=hs[nx][bk[nx]%3];
      bk[nx]++;
    }
  }
  for(int i=0;i<q;i++){
    if(rw[l[i]-1]!=rw[r[i]]){res[i]=false;}
  }
  for(int i=0;i<q;i++){
    if(res[i]){cout << "Yes\n";}
    else{cout << "No\n";}
  }
  return 0;
}