BZOJ2790: [Poi2012]Distance

2790: [Poi2012]Distance

Time Limit: 40 Sec Memory Limit: 128 MB
Submit: 158 Solved: 83
[Submit][Status]

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

HINT

Source

鸣谢 oimaster

题解：
WA了n发终于过了这道题。。。坑点多多啊。。。
首先我们要推出d（x，y）=g[x]+g[y]-2*g[gcd(x,y)]
这是很好推的。
然后我们对于每一个i，gcd（i，？）是可以枚举的，另f[i]表示x%i==0，且g[x]最小的数，然后我们需要最小化g[gcd(i,?)]，
这样我们可以枚举每个数的约数j，更新f[j]即可。最后再扫一遍。因为要i！=j，所以还要保留次大。
坑点:sqrt（a[i]）不能算两次。最小的j满足d(a[i],a[j])最小。。。
代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 1000000+5
 26 
 27 #define maxm 500+100
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 1000000007
 44 
 45 using namespace std;
 46 
 47 inline int read()
 48 
 49 {
 50 
 51     int x=0,f=1;char ch=getchar();
 52 
 53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 54 
 55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 56 
 57     return x*f;
 58 
 59 }
 60 int n,tot,a[maxn],p[maxn],f[maxn][2],g[maxn+1];
 61 
 62 int main()
 63 
 64 {
 65 
 66     freopen("input.txt","r",stdin);
 67 
 68     freopen("output.txt","w",stdout);
 69     for2(i,2,maxn)
 70     {
 71         if(!g[i])p[++tot]=i,g[i]=1;
 72         for1(j,tot)
 73         {
 74             int k=i*p[j];
 75             if(k>maxn)break;
 76             g[k]=g[i]+1;
 77             if(i%p[j]==0)break;
 78         }
 79     }
 80     g[0]=inf;
 81 
 82     n=read();
 83     for1(i,n)a[i]=read();
 84     for3(i,n,1)
 85     {
 86         int x=sqrt(a[i]);
 87         for1(j,x)if(a[i]%j==0)
 88         {
 89             int k=j;
 90             if(g[a[f[k][0]]]>=g[a[i]])f[k][1]=f[k][0],f[k][0]=i;
 91             else if(g[a[f[k][1]]]>=g[a[i]])f[k][1]=i;
 92             if(j*j==a[i])break;
 93             k=a[i]/j;
 94             if(g[a[f[k][0]]]>=g[a[i]])f[k][1]=f[k][0],f[k][0]=i;
 95             else if(g[a[f[k][1]]]>=g[a[i]])f[k][1]=i;
 96         }
 97     }
 98     for1(i,n)
 99     {
100         int x=sqrt(a[i]),tmp=inf>>1,ans=n+1;
101         for1(j,x)if(a[i]%j==0)
102         {
103             int k=j;
104             if(f[k][0]!=i)
105             {
106                 int t=g[a[i]]-2*g[k]+g[a[f[k][0]]];
107                 if(t<tmp||(t==tmp&&f[k][0]<ans))tmp=t,ans=f[k][0];
108             }
109             else
110             {
111                 int t=g[a[i]]-2*g[k]+g[a[f[k][1]]];
112                 if(t<tmp||(t==tmp&&f[k][1]<ans))tmp=t,ans=f[k][1];
113             }
114             k=a[i]/j;
115             if(f[k][0]!=i)
116             {
117                 int t=g[a[i]]-2*g[k]+g[a[f[k][0]]];
118                 if(t<tmp||(t==tmp&&f[k][0]<ans))tmp=t,ans=f[k][0];
119             }
120             else
121             {
122                 int t=g[a[i]]-2*g[k]+g[a[f[k][1]]];
123                 if(t<tmp||(t==tmp&&f[k][1]<ans))tmp=t,ans=f[k][1];
124             }
125         }
126         printf("%d
",ans);
127     }
128 
129     return 0;
130 
131 }

View Code

貌似有关gcd的问题枚举约数是个不错的选择？