Gまでは悪くなかったんだけどね…。
https://atcoder.jp/contests/abc238/tasks/abc238_g
問題
正整数列Aが与えられる。
区間[L,R]からなるクエリが与えられるので、A[L]...A[R]の積が立方数になるか判定せよ。
解法
f(p,n) := 素数p毎に定められるハッシュ値で、以下のように定める
- n=0の時1
- n=1,2では他と衝突しない値
- n = 3k+mの場合、n=mの時と同じ値
数列Aに対し、以下のハッシュ値を考える。
H(n) := A[0]....A[n-1]の積を素因数分解したとき、素数p毎に、その次数をqとしてf(p,q)の積を取ったもの
H(L)=H(R+1)なら、A[L]...A[R]の積における各素因数の次数が3の倍数であり、すなわちその積は立方数とみなせる。
H(n)は累積和など使い前処理で列挙できる。
std::random_device rnd; const int DI=3; int N,Q; ll P[1010101][DI][3]; vector<int> V[1010101]; ll H[1010101][3]; const ll mo=998244353; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; std::mt19937 mt(rnd()); for(i=1;i<=1000000;i++) { FOR(x,DI) { P[i][x][0]=1; P[i][x][1]=1LL*mt()*mt()%mo; P[i][x][2]=1LL*mt()*mt()%mo; } } cin>>N>>Q; FOR(i,N) { cin>>y; for(x=2;x*x<=y;x++) { while(y%x==0) { V[x].push_back(i); y/=x; } } if(y>1) V[y].push_back(i); FOR(x,DI) H[i+1][x]=1; } FOR(x,DI) H[0][x]=1; for(i=2;i<=1000000;i++) { int cur=0; while(cur<V[i].size()) { x=V[i][cur]; int a=cur; while(cur<V[i].size()&&V[i][cur]==x) cur++; FOR(j,DI) { (H[x+1][j]*=modpow(P[i][j][a%3])*P[i][j][cur%3]%mo)%=mo; } } } for(i=1;i<=N;i++) FOR(j,DI) (H[i][j]*=H[i-1][j])%=mo; FOR(i,Q) { cin>>x>>y; x--; FOR(j,DI) if(H[x][j]!=H[y][j]) break; if(j==DI) cout<<"Yes"<<endl; else cout<<"No"<<endl; } }
まとめ
解説にあるxorを使ったハッシュ賢いな…。