Yukicoder014 最小公倍数ソート

問題概要

最小公倍数ソートというものを考える。 まだ整列されていない数列の右端$A$を固定して他の数と$A$との最小公倍数を求め、最小公倍数が最も小さいものを右端に移動させる。 これをソートが完了するまで繰り返す。 最終的な数列を出力せよ。

$N\leqq10^4$、$a[i]\leqq10^4$

yukicoder014

解法

ベースとなる左端の値を$Base$とする。今一番左に動かしたいのは、
$Base * a[x] / gcd(Base,a[x])$が最小となる$a[x]$である。
愚直にやると$O(N^2)$だが、ここで約数について考える。
$a[i]$の約数の上限はたぶん100種もない。
$Base$の持つ約数の集合は、$gcd(Base,a[x])$を必ず含んでいる。
ここで、ある約数を含む、最小の$a[x]$を簡単に検索することができれば この問題は$Base$の約数を全て試すことで次の$a[x]$を決定することができる。
これは最小値の検索が$O(logN)$でできるデータ構造があると高速になる。
最初はヒープでいいじゃんとなったけど、削除も必要なのでsetでこれを行う。

計算量:$O(Nπ(a[i])logπ(a[i]))$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    using PII = pair<int, int>;   using PLL = pair<LL, LL>;
    
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;                          const LL LINF = 1e16;
    
    LL N;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VI a(N);
        VVI divs(N);
    
        vector<set<PII>> S(10001);
        FOR(i, 0, N) {
            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 id = 0;
        FOR(_, 0, N) {
            cout << a[id] << (_ == N - 1 ? "\n" : " ");
    
            PII Min = PII(INF, INF);
            int tempid = -1;
            FOR(i, 0, SZ(divs[id])) {
                S[divs[id][i]].erase(PII(a[id], id));//使っちゃいけないので
                if (S[divs[id][i]].empty())continue;
                PII b = *S[divs[id][i]].begin();
                PII comp = PII(a[id] / divs[id][i] * a[b.second], b.first);
                if (Min > comp) {
                    Min = comp;
                    tempid = b.second;
                }
            }
            id = tempid;
        }
    
        return 0;
    }