首页 > 代码库 > BZOJ2790: [Poi2012]Distance
BZOJ2790: [Poi2012]Distance
2790: [Poi2012]Distance
Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 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
1
2
3
4
5
6
Sample Output
2
1
1
2
1
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])最小。。。
代码：
View Code
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 else110 {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 else121 {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\n",ans);127 }128 129 return 0;130 131 }
貌似有关gcd的问题枚举约数是个不错的选择？
BZOJ2790: [Poi2012]Distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。