mayoko’s diary

プロコンとかいろいろ。

yukicoder No.14 最小公倍数ソート

解法

先に解法を説明してからなんでそれで良いのかを説明する感じでいきます。

まず解法ですが, 最初に 各 ai の約数 div を求めていき, divs[i] という配列にその約数を入れていくと同時に, set を用意して set[div] に (a[i], i) の情報を入れていきます。

で, 実際に最小公倍数ソートするときは, 固定された数の約数 div ごとに, set[div] の第一要素(要するに数が一番小さいやつ)を見ていき, この数と固定された数の最小公倍数を求め, それが最も小さいものを次に固定される数とすれば良いです。

なぜこれで良いかというと, 固定された数と他の数との gcd として考えられる数は, そもそも固定された数の約数しか候補ではないです。そのため, 固定された数の約数ごとに最小のそれを約数として持つ最小の数字が, 最小公倍数を最小にするものの候補になります。よって, 上のアルゴリズムで正しいです。

計算量は, O( N^{1.5}\log N) だと思います。

const int MAXN = 10011;
int a[MAXN];
set<pii> S[MAXN];
vector<int> divs[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        for (int j = 1; j*j <= a[i]; j++) {
            if (a[i]%j == 0) {
                divs[i].push_back(j);
                S[j].insert(pii(a[i], i));
                if (j*j != a[i]) {
                    divs[i].push_back(a[i]/j);
                    S[a[i]/j].insert(pii(a[i], i));
                }
            }
        }
    }
    int index = 0;
    for (int i = 0; i < N; i++) {
        cout << a[index] << " ";
        pii mini(1<<30, 1<<30);
        int id = 0;
        for (int div : divs[index]) {
            S[div].erase(pii(a[index], index));
            if (S[div].empty()) continue;
            pii p = *S[div].begin();
            int tmp = p.first/div * a[index];
            pii q(tmp, p.first);
            if (q < mini) {
                mini = q;
                id = p.second;
            }
        }
        index = id;
    }
    cout << endl;
    return 0;
}