【JZOJ4699】Password

Description

Solution

补坑 因为A序列是个矩阵，所以B序列肯定在A序列里。

首先，B序列中最大的数肯定是A序列最大的，B序列次大的也是A序列中次大的，那么这样想，除了最大和次大的最大公约数外，第三大就是A序列中第三大的。

于是，每次把新加入的答案与之前的两两gcd，去掉的得出的结果（去掉两个）即可。

Code

#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define N 1001 #define mo 3000007 using namespace std; int a[N*N]; int c[N]; int h[mo],z[mo]; bool cmp(int x,int y) { return x>y; } bool find(int x) { int p=x%mo; while(z[p] && z[p]!=x) p=(p+1)%mo; return h[p]; } void hash(int x) { int p=x%mo; while(z[p] && z[p]!=x) p=(p+1)%mo; z[p]=x; h[p]++; } void del(int x,int t) { int p=x%mo; while(z[p] && z[p]!=x) p=(p+1)%mo; if(z[p]==x) { if(t==-1) h[p]=0; else h[p]-=t; h[p]=max(h[p],0); } } int gcd(int x,int y) { int z; while(x%y!=0) { z=x%y; x=y; y=z; } return y; } int main() { int n; cin>>n; fo(i,1,n*n) scanf("%d",&a[i]),hash(a[i]); sort(a+1,a+n*n+1,cmp); fo(i,1,n*n) if(find(a[i])) { c[++c[0]]=a[i]; del(c[c[0]],1); fo(j,1,c[0]-1) del(gcd(c[j],c[c[0]]),2); if(c[0]==n) break; } fo(i,1,c[0]) printf("%d ",c[i]); }