poi2012 distance

暴力水过。。就是d(a,b)=c[a]+c[b]-c[gcd(a,b)];c[i]表示i的质因子数。然后对每个a[i]暴力枚举gcd(),求一个b使c[a]+c[b]-2*c[gcd()]最小。。这个可以预处理后O(1)解决。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxi=1000000000;
int n,m=0,tot=0;
bool ss[1000051];
int prime[1000051];
int f[1000051],g[1000051];
int a[1000051],c[1000051];
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        m=max(m,a[i]);
    }
    memset(ss,true,sizeof(ss));
    for (int i=2;i<=m;i++){
        if  (ss[i]){
            prime[++tot]=i;
            c[i]=1;
        }
        for (int j=1;j<=tot&&prime[j]*i<=m;j++){
            int k=i*prime[j];
            ss[k]=false;
            c[k]=c[i]+1;
            if (i%prime[j]==0) break;
        }
    }
    //for (int i=1;i<=tot;i++) printf("prime[%d]=%d\n",i,prime[i]);
    //for (int i=1;i<=m;i++) printf("c[%d]=%d\n",i,c[i]);
    c[0]=maxi;
    for (int i=1;i<=n;i++){
        for (int j=1;j*j<=a[i];j++){
            if (a[i]%j!=0) continue;
            int k=a[i]/j;
            //printf("i=%d j=%d k=%d\n",i,j,k);
            if (c[a[i]]<c[a[f[j]]]){g[j]=f[j]; f[j]=i;}
            else if (c[a[i]]<c[a[g[j]]]) g[j]=i;
            //printf("g=%d f=%d\n",g[j],f[j]);
            if (j==k) continue;
            if (c[a[i]]<c[a[f[k]]]){g[k]=f[k]; f[k]=i;}
            else if (c[a[i]]<c[a[g[k]]]) g[k]=i;
        }
        //if (i%10000==0) printf("i=%d\n",i);
    }
    //for (int i=1;i<=m;i++) printf("i=%d f=%d g=%d\n",i,f[i],g[i]);
    for (int i=1;i<=n;i++){
        int h=maxi,d=0;
        for (int j=1;j*j<=a[i];j++){
            if (a[i]%j!=0) continue;
            int k=a[i]/j,x;
            if (f[j]==i) x=g[j];
            else x=f[j];
            //printf("i=%d x=%d j=%d k=%d h=%d\n",i,x,j,k,h[i]);
            if (h>c[a[i]]+c[a[x]]-2*c[j]||(h==c[a[i]]+c[a[x]]-2*c[j]&&x<d)){
                h=c[a[i]]+c[a[x]]-2*c[j];
                d=x;
            }
            if (j==k) continue;
            if (f[k]==i) x=g[k];
            else x=f[k];
            if (h>c[a[i]]+c[a[x]]-2*c[k]||(h==c[a[i]]+c[a[x]]-2*c[k]&&x<d)){
                h=c[a[i]]+c[a[x]]-2*c[k];
                d=x;
            }
        }
        //if (i%10000==0) printf("%d\n",i);
        printf("%d\n",d);
    }
}