《CF582A GCD Table》

题目描述

有一个长度为n的数列a，它可以生成一个n∗n的数表，数表的第i行第j列存放的数字是gcd(a[i],a[j]) （即a[i]和a[j]的最大公因数）。

举个例子，上面那个表，就是由数列a[]={4,3,6,2}生成的。

现在我们要做这样一件事情：将这个数表中的这n∗n 个数打乱，得到一个长度为n∗n的序列(可参考样例1)。在已知这个序列的情况下，请还原出数列a。

输入格式

第一行是一个整数n（1≤n≤500），代表的是原数列a的长度。

第二行是n∗n个整数（均不超过109，且均为正数），代表打乱之后的数表的元素。保证有解。

输出格式

共一行n个整数，即您还原出的数组a中的元素。数与数之间用一个空格分隔开。

如果有多个这样的数列a满足题意，只需要输出一组即可。

显示翻译

题意翻译

输入输出样例

输入 #1复制

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

输出 #1复制

4 3 6 2

输入 #2复制

1 42

输出 #2复制

42

输入 #3复制

2 1 1 1 1

输出 #3复制

1 1

代码实现：

#include<bits/stdc++.h> using namespace std; int m,M,x[300005]; int c=0,p[505]; map<int,int> mp; void solve(){ cin>>m;M=m*m; for(int i=1;i<=M;i++) cin>>x[i]; sort(x+1,x+M+1); reverse(x+1,x+M+1); for(int i=1;i<=M;i++){ if(mp[x[i]]){mp[x[i]]--;continue;} p[++c]=x[i]; if(c==m) break; for(int j=1;j<c;j++) mp[__gcd(x[i],p[j])]+=2; } for(int i=1;i<=m;i++) cout<<p[i]<<" "; } int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); solve(); return 0; }