【BZOJ2790】[Poi2012]Distance
Description
对于两个正整数a、b，这样定义函数d(a,b)：每次操作可以选择一个质数p，将a变成a*p或a/p，
如果选择变成a/p就要保证p是a的约数，d(a,b)表示将a变成b所需的最少操作次数。例如d(69,42)=3。
现在给出n个正整数A1,A2,...,An，对于每个i (1<=i<=n)，求最小的j(1<=j<=n)使得i≠j且d(Ai,Aj)最小。
Input
第一行一个正整数n (2<=n<=100,000)。第二行n个正整数A1,A2,...,An (Ai<=1,000,000)。
Output
输出n行，依次表示答案。
Sample Input
6
1
2
3
4
5
6
1
2
3
4
5
6
Sample Output
2
1
1
2
1
2
1
1
2
1
2
题解：我们设s[i]表示i的所有质因子的幂次之和，那么从i变为1的代价就是s[i]，从i变为j的代价就是s[i]+s[j]-s[gcd(i,j)]，然后怎么做呢？
此时最重要的一个思路就是讨论gcd(i,j)对它的倍数的贡献（与和式的改变求和指标类似）
我们枚举i的每个倍数，找出最小的j使得s[j]最小且j在原数列中出现过且出现过的位置最靠前，这样我们就能用j去更新i的其他倍数，但是j用谁来更新呢？于是我们还需要找出一个次大值k，用它来更新j。
此外别忘了判重。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=100010;
const int maxm=1000010;
const int inf=0x3f3f3f3f;
int n,m,num,m1,m2;
int v[maxn],pri[maxn],s[maxm],f[maxm],g[maxm],mn[maxm],next[maxm];
bool np[maxm];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd();
int i,j,k;
memset(f,0x3f,sizeof(f));
for(i=1;i<=n;i++)
v[i]=rd(),next[v[i]]=(mn[v[i]]&&!next[v[i]])?i:next[v[i]],mn[v[i]]=(!mn[v[i]])?i:mn[v[i]],m=max(m,v[i]);
s[1]=0;
for(i=2;i<=m;i++)
{
if(!np[i]) pri[++num]=i,s[i]=1;
for(j=1;j<=num&&i*pri[j]<=m;j++)
{
np[i*pri[j]]=1,s[i*pri[j]]=s[i]+1;
if(i%pri[j]==0) break;
}
}
s[0]=mn[0]=inf;
for(i=1;i<=m;i++)
{
m1=m2=0;
for(j=i;j<=m;j+=i)
{
if(!mn[j]) continue;
if(s[m1]>s[j]||(s[m1]==s[j]&&mn[m1]>mn[j])) m2=m1,m1=j;
else if(s[m2]>s[j]||(s[m2]==s[j]&&mn[m2]>mn[j])) m2=j;
}
for(j=i;j<=m;j+=i)
{
k=(j==m1)?m2:m1;
if(f[j]>s[j]+s[k]-2*s[i]) f[j]=s[j]+s[k]-2*s[i],g[j]=mn[k];
else if(f[j]==s[j]+s[k]-2*s[i]&&g[j]>mn[k]) g[j]=min(g[j],mn[k]);
}
}
for(i=1;i<=n;i++)
{
if(mn[v[i]]==i) printf("%d\n",next[v[i]]?next[v[i]]:g[v[i]]);
else printf("%d\n",mn[v[i]]);
}
return 0;
}