【CF583C】【Password】【数论】

题目大意

有n个数，给出他们两两的gcd（包括自己和自己）n^2个，求这n个数。

解题思路

显然发现最大的那个gcd一定是最大的数，第二大的gcd一定是第二大的数，出去它们gcd的影响，最大的哪一个一定是第三大。以此类推用数据结构存储即可。

可是我想到了一个随机数据下表现优良的水法。大量的实验证明随机数据下不同的gcd大约在1.5n左右，gcd是原数的约数，若有x个gcd是y或y的倍数，则有 x√ 个数是y或y的倍数。所以可以用 (1.5n)2 的复杂度计算影响。

code

#include<set> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const maxn=1000,maxa=1000000000; int n,a[maxn*maxn+10],b[maxn*maxn+10],cnt[maxn*maxn+10],num[maxn*maxn+10]; int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); scanf("%d",&n); fo(i,1,n*n)scanf("%d",&a[i]); sort(a+1,a+n*n+1); fo(i,1,n*n) if(a[i]!=a[i-1])b[++b[0]]=a[i],cnt[b[0]]=1; else cnt[b[0]]++; fd(i,b[0],1){ int cntt=0,numm=0; fo(j,i,b[0]) if(b[j]%b[i]==0)cntt+=cnt[j],numm+=num[j]; num[i]=sqrt(cntt)-numm; fo(j,1,num[i])printf("%d ",b[i]); } return 0; }