BZOJ2790: [Poi2012]Distance 数学+线性筛

题解：

令$num[i]$表示将$i$分解质因数之后所有质因子幂次的和。

则不难发现：$d(x,y)=num[\frac{x}{gcd(x,y)}]+num[\frac{y}{gcd(x,y)}]=num[x]+num[y]-2num[gcd(x,y)]$。

证明可以考虑将每个质因子分开考虑得到。

因此，我们对于每一个$a[i]$，枚举$a[i]$的所有因数$b$，并用所有是$b$的倍数的$a[j]$更新答案。

有人会问如果$b$并不是$gcd(a[i],a[j])$怎么办，这种情况一定不会有枚举到$b=gcd(a[i],a[j])$的时候优，所以枚举进去并不成问题。

我们需要对于每个$b$预处理所有是$b$的倍数的$a[i]$的$num$最小值，若有多个则取标号的最小值，由于$a[i]$自己可能作为答案所以要维护最小和次小。

令$N=10^6$。

这可以暴力做到$O(NlnN)$。

然后进行刚才的计算，时间复杂度为$O(n\sqrt{N})$。

这里涉及到求$num$以及线性求所有约数，都可以利用线性筛处理，详情见代码。

于是就做完了。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
inline int getc(){
    static const int L=1<<15;
    static char buf[L],*S=buf,*T=buf;
    if(S==T){
        T=(S=buf)+fread(buf,1,L,stdin);
        if(S==T)
            return EOF;
    }
    return*S++;
}
 
inline int getint(){
    int c;
    while(!isdigit(c=getc()));
    int x=c-'0';
    while(isdigit(c=getc()))
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
 
typedef pair<int,int> pii;
#define mp make_pair
 
#define N 1000010
int a[100010];
int p[N],lp[N],num[N],cnt;
bool np[N];
void pre(int n){
    int i,j;
    for(i=2;i<=n;++i){
        if(!np[i]){
            p[++cnt]=i;
            num[i]=1;
            lp[i]=i;
        }
        for(j=1;j<=cnt&&p[j]*i<=n;++j){
            np[i*p[j]]=1;
            num[i*p[j]]=num[i]+1;
            lp[i*p[j]]=p[j];
            if(i%p[j]==0)
                break;
        }
    }
}
 
int pri[110],ti[110],id;
void divide(int x){
    for(id=0;x!=1;x/=lp[x]){
        if(lp[x]==pri[id])
            ++ti[id];
        else{
            pri[++id]=lp[x];
            ti[id]=1;
        }
    }
}
 
int sav[N],nums;
void dfs(int dep,int x){
    if(dep>id){
        sav[++nums]=x;
        return;
    }
    for(int i=0;i<=ti[dep];++i,x*=pri[dep])
        dfs(dep+1,x);
}
 
#define inf 0x3f3f3f3f
struct Ans{
    pii mn,_mn;
    Ans():mn(mp(inf,0)),_mn(mp(inf,0)){}
    void upd(int x,int y){
        if(mp(x,y)<mn){
            _mn=mn;
            mn=mp(x,y);
        }
        else if(mp(x,y)<_mn)
            _mn=mp(x,y);
    }
}f[N];
 
int ins[N][2];
 
int main(){
#ifndef ONLINE_JUDGE
    //freopen("tt.in","r",stdin);
#endif
    int n=getint(),i,j,k;
    for(i=1;i<=n;++i)
        a[i]=getint();
    for(i=1;i<=n;++i){
        if(!ins[a[i]][0])
            ins[a[i]][0]=i;
        else if(!ins[a[i]][1])
            ins[a[i]][1]=i;
    }
     
 
    pre(1000000);
     
    for(i=1;i<=1000000;++i)
        for(j=i;j<=1000000;j+=i){
            if(ins[j][0])
                f[i].upd(num[j],ins[j][0]);
            if(ins[j][1])
                f[i].upd(num[j],ins[j][1]);
        }
     
    for(i=1;i<=n;++i){
        divide(a[i]);
        nums=0;
        dfs(1,1);
        pii ans(inf,0);
        for(j=1;j<=nums;++j){
            if(f[sav[j]].mn.second==i)
                ans=min(ans,mp(num[a[i]]-2*num[sav[j]]+f[sav[j]]._mn.first,f[sav[j]]._mn.second));
            else
                ans=min(ans,mp(num[a[i]]-2*num[sav[j]]+f[sav[j]].mn.first,f[sav[j]].mn.second));
        }
        printf("%d\n",ans.second);
    }
     
    return 0;
}