Codeforces Round #323 (Div. 1) A. GCD Table

問題

codeforces.com

解法

数列 a を大きい順に並べた時, と並ぶとします。

この時, GCD table の一番大きな値は と一致します。なぜかというと, 任意の整数 p, q について, gcd(p, q) <= p となるので, もし が GCD table の最大値よりも小さかったとすると, GCD table の最大値を使うことができなくなってしまいます。
ということで, GCD table の一番大きな値は と一致しなければならないのです。

じゃあ の値はどうなるのでしょうか？上で書いたことにより, gcd() <= となるので, やはり残った GCD table のうち最大のものが の値となります。これで数列 a のうち 4 つの値 (2 つ確定したので 2*2 = 4 ですね)が確定したので, GCD table からこれらの値を取り除きましょう。

次の の値からも同様ですね。残った GCD table のうち最大のものを数列 a の値として確定した値をどんどん GCD table から取り除いていけば答えが得られます。

const int MAXN = 555;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    map<int, int> G;
    for (int i = 0; i < n*n; i++) {
        int g;
        cin >> g;
        G[g] += 1;
    }
    vector<int> ans;
    for (int t = 0; t < n; t++) {
        int tmp = -1;
        for (auto it = G.rbegin(); ; it++) {
            if ((*it).second != 0) {
                tmp = (*it).first;
                break;
            }
        }
        G[tmp]--;
        for (int el : ans) {
            G[__gcd(el, tmp)] -= 2;
        }
        ans.push_back(tmp);
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i];
        if (i < n-1) cout << " ";
    }
    cout << endl;
    return 0;
}