ABC469 F - GCD Maximum Spanning Tree

GCD最大全域木

考え方

最大全域木の問題なので、Kruskal法かPrim法を使いたくなる。
しかし、元のグラフの辺数が $O(N^2)$ 本あるため、どちらも間に合わない。
そもそも、辺を $1$ 本ずつ相手にする方法は全てアウトである。

ということで、良い辺を優先的に探す方法を考える。
これは、$A_i$ が最大 $10^6$ しかないというのがヒント。

これを実行するのは、$A[i]$ 側の約数列挙をしていけば簡単。
これで、同じ $k$ の倍数集合に入った頂点同士は、$k$ の辺で結ばれている。
（最大でない公約数の重みの辺が追加で引かれてしまうが、最大値探索には影響がない）

ということで、$k$ が大きい順に同じ $k$ の倍数グループが全部連結になるようにしていけばよい。
全部連結にするには、UnionFind木で連結性を管理しながら行う。

計算量は、$O(A_{\max}+\sum \sqrt{A_i}+\alpha(N) \sum \tau(A_i))$ となる。
ただし、$\alpha(N)$ はアッカーマン関数の逆関数、$\tau(A_i)$ は約数の個数。

入力を受け取る。

n: 3
a: {4, 6, 12}

各 a[i] の約数を列挙し、その約数を持つ頂点番号を vec に記録する。
空でない vec[i] の内容は、次のようになる。

vec[1]: {0, 1, 2}
vec[2]: {0, 1, 2}
vec[3]: {1, 2}
vec[4]: {0, 2}
vec[6]: {1, 2}
vec[12]: {2}

最大全域木を作るため、約数を大きい順に調べる。

$i=6$ のとき、6 を約数に持つ頂点は 1, 2 である。
この $2$ 頂点はまだ連結でないので、UnionFind木で連結し、result に $6$ を加える。

result: 6

$i=4$ のとき、4 を約数に持つ頂点は 0, 2 である。
この $2$ 頂点はまだ連結でないので、UnionFind木で連結し、result に $4$ を加える。

result: 10

これで全頂点が連結になる。
それより小さい約数では新しい連結は行われない。

最後に、result の値である $10$ を出力する。

答えは、int 型からはみ出る。
long long 型を用いること。

特になし。