题目描述
有一个长度为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; }
