原案:vwxyz

クラスカル法ですべての辺を列挙しようとすると実行時間に間に合わないので、工夫する必要があります。
まず、すべての辺の重みは \(\max(A)\) 以下です。
Union-Find 木を用意します。
\(g=\max(A),\max(A)-1,\dots,1\) の順に以下の操作を行います。

• \(A_i\) が \(g\) の倍数であるような \(i\) を列挙する。
• これらの中にまだ連結になっていないものがあれば連結させることを繰り返す。

これによって得られる木が最大全域木になっています。 \(A_i\) と \(A_j\) が \(g\) の倍数のとき、\(\gcd(A_i,A_j)\) は \(g\) に等しいとは限りませんが、\(g\) でないならば\(g\) より大きく、それ以前にすでに結ばれているはずだからです。

前計算によって、\(A\) の添え字を \(A_i\) から逆引きできるようにしておきます。
\(g\) の倍数であるような \(\max(A)\) 以下の正整数は \(\frac{\max(A)}{g}\) 個以下なのですべて調べれば、調和級数の計算量解析により、\(1\) つ目の操作の列挙は \(O(N+\max(A)\log{\max(A)})\) などでできることがわかります。

\(2\) つ目の操作についても、連結させる回数はちょうど \(N-1\) 回です。

全体の計算量は \(O((N+\max(A)\log{\max(A)})α(N))\) です。