[Codeforces] Codeforces Round #669 (Div. 2) B. Big Vova

2020年12月13日

問題

方針

配列 \( a \) を入れ替えて得られる配列を \( b \) とします。ここで、\( g(a, b) \) を \( a, b \) の最大公約数とします。次に配列 \( c \) の \( i \) 番目の要素を

\[ c_i = g(b_1, b_2, \cdots, b_i)\]

とします。このとき、得られる \( c \) の中で辞書式順序が最大であるときの \( b \) を求めます。

まず初めに、\( b_1 = \max(a_1, a_2, \cdots, a_n) \) であることが分かります。ここで、\( g_1 = b_1 \) とします。次に、\( g(g_1, a_i) \) を最大化する \( i \) を求めます。そして、\( b_2 = a_i \) となります。ただし、\( a_i \) は \( b \) の要素に含まれないものとします。同様にして、\( g_2 = g(g_1, a_i) \) とし、\( g(g_2, a_i) \) を最大化するものを求めます。

\( O(N^2) \) の計算量となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[1000];

ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

void solve(int n) {
    sort(a, a + n, greater<int>());
    int ans[n];
    ans[0] = a[0];
    int g = a[0];
    bool f[n]{};
    f[0] = true;
    for (int i = 1; i < n; i++) {
        int idx = i;
        int best = 0;
        for (int j = 1; j < n; j++) {
            if (f[j]) continue;
            if (best < gcd(g, a[j])) {
                best = gcd(g, a[j]);
                idx = j;
            }
        }
        f[idx] = true;
        g = gcd(g, a[idx]);
        ans[i] = a[idx];
    }
    for (int i = 0; i < n; i++) {
        if (i == n - 1) {
            cout << ans[i] << "\n";
        } else {
            cout << ans[i] << " ";
        }
    }
}

int main() {
    int t, n;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }
        solve(n);
    }
    return 0;
}