POI2012 ODL-Distance

链接P3532 [POI2012]ODL-Distance

设$f_{i,j}$表示他给定的函数，$g_i$表示$i$的质因数个数
那么$$f_{i,j}=g_{\frac {i*j}{gcd^2}}$$
考虑线性筛$g_i$。
那么对于每一个数$w_i$考虑枚举他的因子作为$gcd$。
也就是枚举$x$，对于$x$，枚举所有$x$的倍数$y$。
所以我们预处理出$h_x$表示$x$和他的倍数中，$f_x$的最小值的编号。
但是我们在计算$i$这个数的答案的时候，不能用$i$来更新本身。
所以在设$p_x$表示$x$和他的倍数中，$f_x$的次小值的编号。
所以在更新每个位置的答案的时候，我们枚举$gcd$，然后再枚举$gcd$的$h_x$和$p_x$。
假设当前值是$a$，如果$h_x$是本身，就用$p_x$和$a$去更新答案，否则就用$h_x$去更新答案。
即$f_{i,j}=g_i+g_j-2*g_{gcd}$
这样虽然不能保证$x$是$a,b$的$gcd$，但是这样一定不是最优的，$a,b$的$gcd$一定会被枚举到并且成为最优解，所以答案一定会被更新成最优的。

#include<bits/stdc++.h>

#define R register int

#define ll long long

using namespace std;

const int N=1000001;

const int inf=2e9;

int n,Mx,w[N],ans[N];

int tot,c[N],f[N],g[N],cnt[N],Mark[N],prm[N>>2];

int gi(){

    R x=0,k=1;char c=getchar();

    while((c<'0'||c>'9')&&c!='-')c=getchar();

    if(c=='-')k=-1,c=getchar();

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*k;

}

void init(){

	for(R i=2;i<=Mx;++i){

		if(!Mark[i])prm[++tot]=i,c[i]=1;

		for(R j=1;j<=tot&&prm[j]*i<=Mx;++j){

			Mark[i*prm[j]]=1,c[i*prm[j]]=c[i]+1;

			if(i%prm[j]==0)break;

		}

	}

}

int main(){

	freopen("9.in","r",stdin);

	freopen("s.out","w",stdout);

	n=gi();

	for(R i=1;i<=n;++i)w[i]=gi(),Mx=max(Mx,w[i]);

	init(),c[0]=2e9;

	for(R i=1;i<=n;++i){

		for(R j=1;j*j<=w[i];++j){

			if(w[i]%j)continue;

			R k=w[i]/j;

			if(c[w[i]]<c[w[f[j]]])g[j]=f[j],f[j]=i;

			else if(c[w[i]]<c[w[g[j]]])g[j]=i;

			if(j==k)continue;

			if(c[w[i]]<c[w[f[k]]])g[k]=f[k],f[k]=i;

			else if(c[w[i]]<c[w[g[k]]])g[k]=i;

		}

	}

	for(R i=1;i<=n;++i){

		R ans=0,Mn=2e9;

		for(R j=1;j*j<=w[i];++j){

			if(w[i]%j)continue;

			R k=w[i]/j,x=0;

			if(f[j]==i)x=g[j];

			else x=f[j];

			if(Mn>c[w[i]]+c[w[x]]-2*c[j]||(Mn==c[w[i]]+c[w[x]]-2*c[j]&&ans>x))

				Mn=c[w[i]]+c[w[x]]-2*c[j],ans=x;

			if(j==k)continue;

			if(f[k]==i)x=g[k];

			else x=f[k];

			if(Mn>c[w[i]]+c[w[x]]-2*c[k]||(Mn==c[w[i]]+c[w[x]]-2*c[k]&&ans>x))

				Mn=c[w[i]]+c[w[x]]-2*c[k],ans=x;

		}

		printf("%d\n",ans);

	}

    return 0;

}

巴特西

POI2012 ODL-Distance

链接P3532 [POI2012]ODL-Distance

最新文章

热门文章