problem-sulving/CodeForces-1407B.cpp at main · sweetpotatoX/problem-sulving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//
// Created by abdob on 10/29/2022.
//

#include<bits/stdc++.h>
#include<stdio.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;


#define ll                  long long
#define scl(n)              scanf("%lld",&n)
#define scll(n, m)          scanf("%lld%lld",&n, &m)
#define scc(c)	            scanf("%c",&c)
#define fr(i,n)             for (ll i=0;i<n;i++)
#define fr1(i,n)            for(ll i=1;i<=n;i++)
#define pfl(x)              printf("%lld\n",x)
#define pb                  push_back
#define debug               cout<<"I am here"<<endl;
#define pno                 cout<<"NO"<<endl
#define pys                 cout<<"YES"<<endl
#define tcas(i,t)           for(ll i=1;i<=t;i++)
#define pr                  pair<ll, ll>
#define ff                  first
#define ss                  second
#define pn                  printf("\n")

#define asort(a)            sort(a,a+n)
#define dsort(a)            sort(a,a+n,greater<int>())
#define uniquee(x)          x.erase(unique(x.begin(), x.end()),x.end())
#define el                  cout<<endl
#define md                  1000000007
#define inf                 1e18
#define ps                  cout<<" ";
#define Pai                 acos(-1.0)
#define mem(a,i)            memset(a, i, sizeof(a))

int main()
{
    ll t;
    scl(t);
    while(t--)
    {
        ll m,n,b,c,d,i,j,k,x,y,z,l,r, p, q;
        string s,s1, s2, s3, s4;

        ll cnt=0,cn=0,ans=0,sum=0 ;
        cin>>n;

        ll a[n];

        fr(i,n)cin>>a[i];
        dsort(a);
        ll vis[n];
        mem(vis , 0);

        vis[n-1]=1;

        vector<ll>v , v1;
        v.pb( a[0] );

        asort(a);

        ll mx=0;
        fr(i , n)
        {
            k=v.size()-1;
            p=-1  ;
            ll gcd=0;

            fr(j , v.size())mx=__gcd(mx , v[j]);

            fr(j , n-1)
            {
                if(! vis[ j  ])
                {
                    if(gcd <  __gcd(mx , a[j] ))
                    {
                        gcd=__gcd(mx  , a[j] );

                        if(p!=-1) vis[p]=0;

                        vis[j]=1;
                        p=j;
                    }
                }
            }
            if(p!=-1) v.pb(a[p] );
        }


        fr(i , v.size())cout<<v[i]<<" ";pn;
    }

    return 0;
}