yukicoder 0014 最小公倍数ソート

問題文

概要

数列 $a_1, \dots, a_n$ が与えられる. $i = 1, \dots, n-1$ に対し, 次の操作を順に行う.

最終的な $a_1, \dots, a_n$ を答えよ.

制約

$1 \le N \le 10^4$, $1 \le a_i \le 10^4$.

解法

どうせ次の数以降はまた別の基準でソートされるので, 一々ソートする必要はなくて, min だけとれればよい. 従って, 次の操作に対応する何かがあればよい:

これを, 値の範囲が小さい事を利用して, 次のようにして作る.

計算量は, $D$ を $A$ 以下の数の約数の個数の最大値として $O(N \sqrt{A} + N D)$.

ここで $\sqrt{A}$ の部分は約数列挙の所で, これは前処理 $O(N)$ で $O(D)$ に落とせるので, $O(ND)$ でも行ける.

$D$ は $o(A^\epsilon), \forall \epsilon > 0$ とかだったハズで, ちっちゃい. この辺, 解析的整数論のにおいがしてヤバいですね.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
constexpr int N = 11000;
bool solve(){
    int n; cin >> n;
    vector<int> a(n); for(aur x : a) cin >> x;
    array<int, N> c = {};
    for(aur x : a) ++c[x];
    int last = a[0]; --c[last];

    array<vector<int>, N> fac;
    array<vector<int>, N> rev;
    for(aur x : a) if(fac[x].empty()){
        fac[x] = factors(x);
        for(auto &f : fac[x]) rev[f].emplace_back(x);
    }
    for(aur x : rev) sort(rall(x));

    vector<int> res;
    res.eb(last);
    rep(_, n-1){
        pair<int, int> nex = make_pair(numeric_limits<int>::max(), 0);
        for(aur f : fac[last]){
            while(!rev[f].empty() and !c[rev[f].back()]) rev[f].pop_back();
            if(rev[f].empty()) continue;
            chmin(nex, make_pair(lcm(last, rev[f].back()), rev[f].back()));
        }
        last = nex.snd;
        --c[last];
        res.eb(last);
    }
    rep(i, n) cout << res[i] << (i == n-1 ? "\n" : " ");
    return true;
}
download full source code

Tags

yukicoder
数論

Comments

comments powered by Disqus