题意:有一个长度为\(n\)的序列,你需要对其重新排序,构造一个新数组\(c\),\(c_{i}=gcd(a_{1},…,a{i})\)并且使得\(c\)的字典序最小.

题解:直接跑\(n\)次,每次找一个目前最大的\(gcd\)出来,并标记位置模拟一下就好了.

代码:

int t;
int n;
int a[N],b[N];
int st[N];

int main() {
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    t=read();
    while(t--){
        n=read();
        me(st,0,sizeof(st));
        for(int i=1;i<=n;++i){
            a[i]=read();
        }
        int now=0;
        for(int i=1;i<=n;++i){
            int mx=0;
            int pos=-1;
            for(int j=1;j<=n;++j){
                int tmp=__gcd(a[j],now);
                if(tmp>mx && !st[j]){
                    mx=tmp;
                    pos=j;
                }
            }
            now=mx;
            st[pos]=true;
            printf("%d ",a[pos]);
        }
        puts("");
    }
return 0;
}