题目概述

有一个序列 $\{a_n\}$ ，如果区间 $[L,R]$ 里存在 $i<j$ 使得 $a_ia_j$ 是完全平方数就称这个区间是好的。一次操作可以把一个数变成 $a_ip$ 或 ${a_i\over p}(p|a_i)$ ( $p$ 是素数)。有 $q$ 个询问，每次询问 $[L,R]$ 至少需要多少次操作变成好的。

解题报告

很明显只会操作两个数，所以答案不超过 $14$ 。先考虑离线，然后从左往右做，如果我们能够处理出 $ML_i$ 表示目前操作次数为 $i$ 的最大的左端点，那么就可以 $O(14)$ 回答。

对于一个数 $a_i$ 的每个素数最多只会乘上一次（乘和除其实没有任何区别），我们可以爆枚乘上哪些素数从而达到另一个数来更新 $ML$ ，但是虽然一个数的素数不多，$n$ 个数的素数就很多了，并不能爆枚……

由于乘和除没有任何区别，所以我们可以先把所有 $a_i$ 的平方因子都删掉，然后问题简化为把 $a_i,a_j$ 变成相同的数。这样就可以记录 $MAX_{i,j}$ 表示用 $j$ 次操作造出 $i$ 的数的最大位置，用 $MAX$ 更新 $ML$ 就好了。

示例程序

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=194598,maxq=1049658,maxa=5032107,maxp=14;

int n,m,A[maxa+5],a[maxn+5],MAX[maxa+5][maxp+5],ML[maxp+5],ans[maxq+5];
int dis[maxa+5];bool vis[maxa+5];vector<int> q[maxn+5],ID[maxn+5],D[maxa+5];

inline void Make(){
    for (int i=1;i<=maxa;i++) A[i]=1;for (int i=1;i*i<=maxa;i++) for (int j=i*i;j<=maxa;j+=i) D[j].push_back(i);
    for (int i=2;i<=maxa;i++)
        for (int j=i;!vis[i]&&j<=maxa;j>i?(vis[j]=true,j+=i):j+=i)
            {int x=j,tot=0;while (!(x%i)) x/=i,tot++,dis[j]++;if (tot&1) A[j]*=i;}
}
#define D(i,j) (D[a[i]][j])
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    Make();scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=A[a[i]];
    for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),q[y].push_back(x),ID[y].push_back(i);
    for (int i=1;i<=n;i++){
        for (int j=0,si=D[a[i]].size();j<si;j++){
            for (int k=0,now=dis[a[i]/D(i,j)];k+now<=maxp;k++) ML[k+now]=max(ML[k+now],MAX[D(i,j)][k]);
            for (int k=0,now=dis[D(i,j)];k+now<=maxp;k++) ML[k+now]=max(ML[k+now],MAX[a[i]/D(i,j)][k]);
        }
        for (int j=0,si=D[a[i]].size();j<si;j++)
            MAX[D(i,j)][dis[a[i]/D(i,j)]]=i,MAX[a[i]/D(i,j)][dis[D(i,j)]]=i;
        for (int j=0,si=q[i].size();j<si;j++)
            for (int k=0;k<=maxp;k++) if (ML[k]>=q[i][j]) {ans[ID[i][j]]=k;break;}
    }for (int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}