Given a sequence $A$ of $N$ numbers, answer the following $Q$ questions. Here, a positive integer $x$ is said to be a cubic number when there is a positive integer $y$ such that $x=y^3$.Problem Statement
Constraints
Input
Input is given from Standard Input in the following format:
$N$ $Q$ $A_1$ $A_2$ $\dots$ $A_N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$
Output
Print $Q$ lines.
The $i$-th line should contain Yes if, in the $i$-th question, $A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i}$ is a cubic number, and No otherwise.
The checker is case-insensitive; output can be either uppercase or lowercase.
Sample Input 1
8 5 7 49 30 1 15 8 6 10 1 2 2 3 4 4 5 8 3 8
Sample Output 1
Yes No Yes No Yes
- For the first question, $7 \times 49 = 343$ is a cubic number.
- For the second question, $49 \times 30 = 1470$ is not a cubic number.
- For the third question, $1$ is a cubic number.
- For the fourth question, $15 \times 8 \times 6 \times 10 = 7200$ is not a cubic number.
- For the fifth question, $30 \times 1 \times 15 \times 8 \times 6 \times 10 = 216000$ is a cubic number.
一个有亿种方法的题目。
什么情况下乘积为立方数？当且仅当分解后所有的素数的指数都是3的倍数。 \(A_i\le 10^6\)，所以先预处理出每一种数的各种质因子。
法一：莫队
这就不用说了吧。加入时枚举每个质因子，维护有多少个质因子的指数模3余0。复杂度 \(O(n\sqrt{n}logn)\)，3秒钟已经是能过得了。
法二：普通哈希
给每个质数分配一个随机权值 \(g_i\)，如果前 \(i\) 个数质数 \(i\) 指数 \(p_i\) 模 3 为 \(k_i\)，那么定义 \(hash(1,n)=\sum\limits_{j=1}^{10^6}g_ik_i\)。处理出前缀 \(h_i=hash(1,i)\)，因为 \(h_i\) 到 \(h_{i+1}\) 会变化的就是在每个因数中加了或减去几个随机权值。若 \([l,r]\) 符合条件，那么 \(h_{l-1}=h_r\)。判断即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,P=998244353;
int n,q,a[N],l,r,pri[N],c[N],op;
long long s[N],f[N];
vector<int>g[N];
int main()
{
srand(time(0));
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=1;i<N;i++)
f[i]=1LL*rand()*rand()%P;
for(int i=2;i<N;i++)
{
if(!pri[i])
{
g[i].push_back(i);
for(int j=2;j*i<N;j++)
g[j*i].push_back(i),pri[j*i]=1;
}
}
for(int i=1;i<=n;i++)
{
s[i]=s[i-1];
for(int j=0;j<g[a[i]].size();j++)
{
int k=a[i],cnt=0;
while(k%g[a[i]][j]==0)
k/=g[a[i]][j],++cnt;
op=((c[g[a[i]][j]]+cnt)%3-c[g[a[i]][j]]%3);
c[g[a[i]][j]]+=cnt;
(s[i]+=(1LL*f[g[a[i]][j]]*op%P+P)%P)%=P;
}
}
while(q--)
{
scanf("%d%d",&l,&r);
if(s[r]==s[l-1])
printf("Yes\n");
else
printf("No\n");
}
}