GCD Table

GCD Table

Problem

Input

Output

Examples

Input

4
2 1 2 3 4 3 2 6 1 1 2 2 1 2 3 2

Output

4 3 6 2

Input

1
42

Output

42 

Input

2
1 1 1 1

Output

1 1 

Code

// #include <iostream>
// #include <algorithm>
// #include <cstring>
// #include <stack>//栈
// #include <deque>//堆/优先队列
// #include <queue>//队列
// #include <map>//映射
// #include <unordered_map>//哈希表
// #include <vector>//容器，存数组的数，表数组的长度
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define endl '\n'
const ll N=1e5+10;
ll a[N];

ll gcd(ll a,ll b)
{
    if(!b) return a;
    else return gcd(b,a%b);
}

void solve()
{
    ll n;
    cin>>n;

    map<ll,ll> m;
    vector<ll> v;
    for(ll i=1;i<=n*n;i++)
    {
        ll x;
        cin>>x;
        if(!m[x]) v.push_back(x);
        m[x]++;
    }

    sort(v.begin(),v.end());
    
    ll cnt=0;
    for(ll i=v.size()-1;i>=0&&cnt<n;)
    {
        if(!m[v[i]]) i--;
        a[++cnt]=v[i];
        m[v[i]]--;
        for(ll j=1;j<cnt;j++) m[gcd(v[i],a[j])]-=2;
    }

    for(ll i=1;i<=cnt;i++) cout<<a[i]<<" ";
    cout<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    ll t=1;
    //cin>>t;
    while(t--) solve();
    
    return 0;
}