​L：最大公约数

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

Captorry\tt{Captorry}Captorry 很喜欢数论。

一天，他拿到了 nnn 个数 a1,a2,…,ana_1,a_2,\dots,a_na1​,a2​,…,an​ 并且算出了他们两两间（包括自己和自己）的 gcd⁡\gcdgcd（最大公约数），即所有的  gcd⁡(i,j)(1≤i≤n,1≤j≤n)\gcd(i,j)(1 \le i\le n,1\le j\le n)gcd(i,j)(1≤i≤n,1≤j≤n) ，一共 n2n^2n2 个数。

但是万恶的 mep\tt{mep}mep 学长抹去了这 nnn 个数并随机打乱了这 n2n^2n2 个 gcd⁡\gcdgcd ，现在 Captorry\tt{Captorry}Captorry 想让你帮他还原出这 nnn 个数。

将你还原的 nnn 个数从小到大输出。

输入描述:

第一行一个正整数 n (1≤n≤1000)n\ (1 \le n \le 1000)n (1≤n≤1000) 表示开始 Captorry\tt{Captorry}Captorry 拿到的数的数量。

第二行 n2n^2n2 个数 ai (1≤ai≤109)a_i\ (1 \le a_i \le 10^9)ai​ (1≤ai​≤109) 表示这些数两两的 gcd⁡\gcdgcd ，注意我们并不知道每个数是哪两个数的 gcd⁡\gcdgcd 。

输出描述:

一行从小到大 nnn 个数，表示你还原的答案。

思路：首先，n^2个数中最大的两个数一定等于 an−1 和 an ，所以我们把gcd(an−1,an) 这个数和an−1 和 an从序列中除去，接下来的思路类似，在序列中选出最大的数作为 an−2 ，并计算与an−1和 an 的gcd，从序列中除去，以此类推。

#include <bits/stdc++.h>
using namespace std;
int n,a[1000001],ans[1003];
map<int ,int> mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    int m=n*n,k=n;
    for (int i=1;i<=m;i++) 
    {
        cin>>a[i];
        mp[a[i]]++;
    }
    sort(a+1,a+m+1);
    ans[k--]=a[m];
    mp[a[m]]--;
    for (int i=m-1;i>0;i--)
    {
        if (mp[a[i]]<=0) continue;
        
        for (int j=k+1;j<=n;j++)
        {
            int t=gcd(a[i],ans[j]);
            mp[t]-=2;//易错
        }
        ans[k--]=a[i];
        mp[a[i]]--;
    }
    for (int i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}