CF582A GCD Table

题目描述

有一个长度为$n$的数列$a$，它可以生成一个$n*n$的数表，数表的第$i$行第$j$列存放的数字是$\gcd(a[i],a[j])$ （即$a[i]$和$a[j]$的最大公因数）。

举个例子，上面那个表，就是由数列$a[]=\{4,3,6,2\}$生成的。

现在我们要做这样一件事情：将这个数表中的这$n*n$ 个数打乱，得到一个长度为$n*n$的序列(可参考样例1)。在已知这个序列的情况下，请还原出数列$a$。

输入格式

第一行是一个整数$n$（$1\leq n\leq500$），代表的是原数列$a$的长度。

第二行是$n*n$个整数（均不超过$10^9$，且均为正数），代表打乱之后的数表的元素。保证有解。

输出格式

共一行$n$个整数，即您还原出的数组$a$中的元素。数与数之间用一个空格分隔开。

如果有多个这样的数列$a$满足题意，只需要输出一组即可。

输入输出样例 #1

输入 #1

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

输出 #1

4 3 6 2

输入输出样例 #2

输入 #2

1
42

输出 #2

42

输入输出样例 #3

输入 #3

2
1 1 1 1

输出 #3

1 1

首先应该想到在这n*n个数中，最大的那个数不可能是谁和谁的gcd，所以一开始最大的那个数必然是原序列的数，次大也一样，首先用map存每个数出现的次数，可以每次找到最大的数，这个就是原序列的数，然后p[mmax]–,然后用这个最大的数和之前已经选好的原序列的数逐个gcd，gcd出来的数次数-=2(妙的思想)，因为是表格，对称的，所以-=2

const int N = 1e6 + 10;
int a[N];
int ans[N];
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
void solve()
{
    int n; cin >> n;
    map<int, int> p;
    for (int i = 1; i <= n * n; i++) cin >> a[i], p[a[i]]++;
    int h = 0;
    for (int i = 1; i <= n; i++)
    {
        int mmax = 0;
        for (auto q : p)
        {
            if (q.second > 0) mmax = max(mmax, q.first);
        }
        p[mmax]--;
        ans[++h] = mmax;
        for (int j = 1; j <= h - 1; j++)
        {
            p[gcd(ans[h], ans[j])] -= 2;
        }
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
    cout << '\n';
}