传送门
题目大意
有一个长度为的数列,它可以生成一个的数表,数表的第行第列存放的数字是 即和的最大公因数。
一个例子:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5CMycjM4cTM1UGOlZWZjBDZyYzX2QDMyATM1EzLcdDMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
举个例子,上面那个表,就是由数列生成的。
思路
代码
ll gcd(ll a,ll b){
return !b?a:gcd(b,a%b);
}
int a[maxn],b[maxn];
map<int,int>mp;
map<int,int>::iterator it;
int cmp(int a,int b){
return a>b;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n*n;i++){
scanf("%d",&a[i]);
mp[a[i]]++;
}
sort(a+1,a+1+n*n,cmp);
int cnt=0;
for(int i=1;i<=n*n;i++){
if(!mp[a[i]]) continue;
mp[a[i]]--;
for(int j=1;j<=cnt;j++){
mp[gcd(a[i],b[j])]-=2;
}
b[++cnt]=a[i];
}
for(int i=1;i<=cnt;i++){
printf("%d ",b[i]);
}
}