Original proposer: vwxyz

We cannot enumerate all edges to apply Kruskal’s algorithm within the execution time limit, so we need to optimize it.
First, all edges have a weight of at most \(\max(A)\).
Prepare a DSU (Disjoint Set Union) tree.
For \(g=\max(A),\max(A)-1,\dots,1\) in order, perform the following operation:

• Enumerate all \(i\) such that \(A_i\) is a multiple of \(g\).
• While they are not connected, repeatedly connect them.

The tree obtained by this procedure is a maximum spanning tree because, when \(A_i\) and \(A_j\) is a multiple of \(g\), \(\gcd(A_i,A_j)\) is not necessarily equal to \(g\), but if it is not \(g\), then it is greater than \(g\), and should have been connected beforehand.

Perform precalculation so that one can obtain the index in \(A\) for any given \(A_i\).
The number of positive integers not exceeding \(\max(A)\) that are multiples of \(g\) is at most at most \(\frac{\max(A)}{g}\), so by the analysis using the harmonic series, the enumeration step in the former step can be done in about \(O(N+\max(A)\log{\max(A)})\) time.

For the second operation, we perform the connection exactly \((N-1)\) times.

The total time complexity is \(O((N+\max(A)\log{\max(A)})α(N))\).