poi2012 distance
stupid_lulu
posted @ 2013年3月24日 15:16
in poi
, 1615 阅读
暴力水过。。就是d(a,b)=c[a]+c[b]-c[gcd(a,b)];c[i]表示i的质因子数。然后对每个a[i]暴力枚举gcd(),求一个b使c[a]+c[b]-2*c[gcd()]最小。。这个可以预处理后O(1)解决。。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxi=1000000000; int n,m=0,tot=0; bool ss[1000051]; int prime[1000051]; int f[1000051],g[1000051]; int a[1000051],c[1000051]; int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&a[i]); m=max(m,a[i]); } memset(ss,true,sizeof(ss)); for (int i=2;i<=m;i++){ if (ss[i]){ prime[++tot]=i; c[i]=1; } for (int j=1;j<=tot&&prime[j]*i<=m;j++){ int k=i*prime[j]; ss[k]=false; c[k]=c[i]+1; if (i%prime[j]==0) break; } } //for (int i=1;i<=tot;i++) printf("prime[%d]=%d\n",i,prime[i]); //for (int i=1;i<=m;i++) printf("c[%d]=%d\n",i,c[i]); c[0]=maxi; for (int i=1;i<=n;i++){ for (int j=1;j*j<=a[i];j++){ if (a[i]%j!=0) continue; int k=a[i]/j; //printf("i=%d j=%d k=%d\n",i,j,k); if (c[a[i]]<c[a[f[j]]]){g[j]=f[j]; f[j]=i;} else if (c[a[i]]<c[a[g[j]]]) g[j]=i; //printf("g=%d f=%d\n",g[j],f[j]); if (j==k) continue; if (c[a[i]]<c[a[f[k]]]){g[k]=f[k]; f[k]=i;} else if (c[a[i]]<c[a[g[k]]]) g[k]=i; } //if (i%10000==0) printf("i=%d\n",i); } //for (int i=1;i<=m;i++) printf("i=%d f=%d g=%d\n",i,f[i],g[i]); for (int i=1;i<=n;i++){ int h=maxi,d=0; for (int j=1;j*j<=a[i];j++){ if (a[i]%j!=0) continue; int k=a[i]/j,x; if (f[j]==i) x=g[j]; else x=f[j]; //printf("i=%d x=%d j=%d k=%d h=%d\n",i,x,j,k,h[i]); if (h>c[a[i]]+c[a[x]]-2*c[j]||(h==c[a[i]]+c[a[x]]-2*c[j]&&x<d)){ h=c[a[i]]+c[a[x]]-2*c[j]; d=x; } if (j==k) continue; if (f[k]==i) x=g[k]; else x=f[k]; if (h>c[a[i]]+c[a[x]]-2*c[k]||(h==c[a[i]]+c[a[x]]-2*c[k]&&x<d)){ h=c[a[i]]+c[a[x]]-2*c[k]; d=x; } } //if (i%10000==0) printf("%d\n",i); printf("%d\n",d); } }
2024年2月21日 23:57
i am for the first time here. I found this board and I in finding It truly helpful & it helped me out a lot. I hope to present something back and help others such as you helped me.