2790: [Poi2012]Distance
Time Limit: 40 Sec Memory Limit: 128 MB
Submit: 225 Solved: 115
[Submit][Status][Discuss]
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
HINT
Source
很容易推出来 $d(x,y)=g(x)+g(y)-2*g(\gcd(x,y))$ 其中g(x)表示x是几个质数的乘积
$g$函数只需要一个线性筛就能求出来，对于$a_i$，$g(a_i)$是固定的，重点在于最小化$g(y)-2*g(gcd(x,y))$
可以枚举$a_i$的因子$x$，用$f[x]$表示是$x$的倍数的$a[j]$使得$g[a[j]]$最小的数
因为要求$i≠j$,所以得维护最小值和次小值，时间复杂度$O(n\sqrt m+m)$ $m=\max{a_i}$
PS:今天BZOJ居然卡住了，管理员今天不在吗？
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
#define M 1000010
int prime[M],tot,g[M];
inline void pre(int t)
{
g[]=1e9;
for(int i=;i<=t;i++)
{
if(!g[i])prime[++tot]=i,g[i]=;
for(int j=;j<=tot&&i*prime[j]<=t;j++)
{
g[i*prime[j]]=g[i]+;
if(!(i%prime[j]))break;
}
}
}
int n,a[N],f[M][],maxn;
inline void update(int x,int i)
{
if(g[a[x]]<=g[a[f[i][]]])
f[i][]=f[i][],f[i][]=x;
else if(g[a[x]]<=g[a[f[i][]]])
f[i][]=x;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]),maxn=max(a[i],maxn);
pre(maxn);
for(int i=n;i;i--)
{
for(int j=;j*j<=a[i];j++)
if(!(a[i]%j))
{
update(i,j);
if(j*j!=a[i])
update(i,a[i]/j);
}
}
for(int i=;i<=n;i++)
{
int ans=1e9,tmp=1e9;
for(int j=;j*j<=a[i];j++)
if(!(a[i]%j))
{
int k=j,x;
if(f[k][]!=i)x=f[k][];
else x=f[k][];
int t=g[a[x]]-*g[k];
if(t<ans||(t==ans&&x<tmp))
ans=t,tmp=x;
k=a[i]/j;
if(f[k][]!=i)x=f[k][];
else x=f[k][];
t=g[a[x]]-*g[k];
if(t<ans||(t==ans&&x<tmp))
ans=t,tmp=x;
}
printf("%d\n",tmp);
}
}