【NOIP2016提高A组模拟8.15】Password

输入

第一行一个数N 第二行N*N个数

输出

N个数，答案

样例输入

4 1 1 2 2 3 4 6 2 2 1 3 2 2 1 3 2

样例输出

6 4 3 2

题解

显然答案中的数必定是原序列中的数， 将原序列排序后，ans[1]=a[1],ans[2]=a[2]，这也是显然的，那ans[3]是第三大的数吗？ 不一定，可能是ans[1]与ans[2]的GCD 这也不难解决，每次求出答案后，把与之前的GCD在桶中标记一下就行了

代码

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define mo 1009999 #define ll long long using namespace std; ll n,a[1010000],ans[10100],bz[1010000],has[1010000]; bool cnt(ll a,ll b){return a>b;} ll gcd(ll m,ll n) { int r=m%n; for(;r!=0;r=m%n,m=n,n=r); return m; } int hash(ll x) { int a=x; for(x=x%mo+1;has[x]!=0&&has[x]!=a;x=x%mo+1); has[x]=a;return x; } int main() { freopen("password.in","r",stdin); scanf("%lld",&n); int x=1; fo(i,1,n*n) scanf("%lld",&a[i]); sort(a+1,a+n*n+1,cnt); ans[1]=a[1];ans[2]=a[2];int j=2; bz[hash(gcd(a[1],a[2]))]+=2; fo(i,3,n*n) { ll k=hash(a[i]); if(bz[k]>0) bz[k]--; else{ ans[++j]=a[i]; fo(l,1,j) bz[hash(gcd(ans[l],ans[j]))]+=2; } } fo(i,1,n) printf("%lld ",ans[i]); }