题面

闲聊

暴力分也给的太少了，刁钻

而且为什么菲鲁特不配拥有姓名？？给我菲鲁特宝一个大大的姓名

好了不BB了

第一题都挂我也不配拥有姓名。。

分析

其实你会发现密码串b的gcd会构成一个N*N的gcd矩阵，而对角线上的数字正是b序列

而这个gcd矩阵其实就是未被打乱前的a序列

而又要满足不下降，还有一个很显然的结论 a,b≤gcd(a,b)

因此b[1]一定是矩阵中最大的数（默认数组从1开始编号），b[2]一定是第二大的。(对角线上数的需要满足不上升，所以一定比他们小。而比他们小的数的gcd也比他们小）

那么b[3]是否是第三大呢？不一定。除了b[1]和b[2]之外，只可能b[1]和b[2]的gcd比它大。

因此衍生出去，当我们每次求到一个b[i]后，需要把a序列中的gcd(b[i],b[j]）(j≤i)全部删掉（每次删两个），再找到一个最大的作为b[i+1]

因为a_i在1e9以内，所以又得用map这坑货

复杂度：O(?² LogN)

代码

#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define RT register
int n,n2,cnt;
int a[N*N],b[N],ans[N],bc[N];
map<int,int>mp;
template<class T>
inline void read(T &x)
{
    x=0;int f=1;static char ch=getchar();
    while(ch<'0'||ch>'9'){       if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
inline int gcd(int a,int b){       return b?gcd(b,a%b):a;}
int main()
{
    read(n);n2=n*n;
    for(RT int i=1;i<=n2;++i)read(a[i]),mp[a[i]]++;
    sort(a+1,a+1+n2);
    for(RT int i=n2;i>=1;i--)
        while(mp[a[i]])
        {
            ans[++cnt]=a[i];mp[a[i]]--;
            for(int j=1;j<cnt;j++)  mp[gcd(a[i],ans[j])]-=2;
        }
    for(RT int i=1;i<=n;++i)printf("%d ",ans[i]);
    return 0;
}