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}

各値の約数ごとに、その約数を持つ頂点をまとめる。
空でないものは次のようになる。

1: {0, 1, 2}
2: {0, 1, 2}
3: {1, 2}
4: {0, 2}
6: {1, 2}
12: {2}

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

$12$ を約数に持つのは頂点 $2$ だけなので、まだ何も連結しない。

次に $6$ を約数に持つ頂点は $1,2$ である。
この $2$ 頂点はまだ別の連結成分なので、重み $6$ の辺として連結する。
この時点での重みの合計は $6$ である。

次に $4$ を約数に持つ頂点は $0,2$ である。
この $2$ 頂点もまだ別の連結成分なので、重み $4$ の辺として連結する。
重みの合計は $6+4=10$ となる。

これで $3$ 頂点すべてが連結した。
以降の小さい約数では新しい連結は発生しないので、答えは $10$ となる。

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

特になし。