Codeforces #323 div2 C. GCD Table 數論 構造

題目

題目連結：http://codeforces.com/problemset/problem/582/A

題目來源：CF #323 div2 C/ div1 A

簡要題意：無序給定序列 a1,a2⋯an 的 gcd 表，求序列

資料範圍： 1 ⩽ n ⩽ 500;0<ai⩽109

題解

由于 gcd(x,y)⩽x,y 并且 gcd(x,x)=x 可以知道排序後最大的數一定是序列中的數。

不妨從大到小構造序列，當得到一個新的數，将這個數與之前得到的數的 gcd 删除。

不斷将最大的 gcd 添加入序列，直到沒有可以取的數為止。

使用數學歸納法可以證明每次得到的數都必須存在于序列之中，因為表中剩餘的數都不超過這個數。

一個很容易想到的結論是奇數個的必然存在于序列中，但是從這個方向思考容易走向死胡同。

實作

可以利用一個map來維護剩餘的 gcd

先存入所有的 gcd 再不斷删除，構造出答案。

代碼

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
LL powmod(LL a,LL b, LL MOD) {LL res=;a%=MOD;for(;b;b>>=){if(b&)res=res*a%MOD;a=a*a%MOD;}return res;}
// head
const int N = *+;

int a[N];
int gcd(int u, int v) {
    return v ? gcd(v, u%v) : u;
}

map<int, int> ma;
vector<int> res;
int main()
{
    int n;
    scanf("%d", &n);
    int m = n*n;
    for (int i = ; i < m; i++) {
        scanf("%d", a+i);
        ma[a[i]]++;
    }
    sort(a, a+m);
    m = unique(a, a+m)-a;

    for (int i = m-; i > -; i--) {
        if (ma[a[i]] == ) continue;
        ma[a[i]]--;
        int len = res.size();
        for (int j = ; j < len; j++) {
            ma[gcd(res[j], a[i])] -= ;
        }
        res.pb(a[i]);
        if (ma[a[i]]) i++;
    }

    int len = res.size(), temp;
    for (int j = ; j < len; j++) {
        printf("%d%c", res[j], j==len-?'\n':' ');
    }
    return ;
}