【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

Sample Output

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;

}

巴特西

【BZOJ2790】[Poi2012]Distance 筛素数+调和级数