D. MST in Modulo Graph
constructive algorithms; dsu; graphs; greedy; math; number theory; sortings; trees
You are given a complete graph with \(n\) vertices, where the \(i\)-th vertex has a weight \(p_i\). The weight of the edge connecting vertex \(x\) and vertex \(y\) is equal to \(\operatorname{max}(p_x, p_y) \bmod \operatorname{min}(p_x, p_y)\).Find the smallest total weight of a set of \(n - 1\) edges that connect all \(n\) vertices in this graph.
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 10^4\)). The description of the test cases follows. The first line of each test contains an integer \(n\) (\(1 \le n \le 5 \cdot 10^5\)).The next line of each test contains \(n\) integers \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le 5 \cdot 10^5\)).The sum of \(n\) over all test cases does not exceed \(5 \cdot 10^5\).The sum of \(\max(p_1,p_2,\ldots,p_n)\) over all test cases does not exceed \(5 \cdot 10^5\).
For each test case, output a single integer — the weight of the minimum spanning tree.
In the first test case, one of the possible ways to connect the edges is to draw the edges \((1, 2)\), \((1, 4)\), \((1, 5)\), \((2, 3)\). The weight of the first edge is \(\operatorname{max}(p_1, p_2) \bmod \operatorname{min}(p_1, p_2)=4 \bmod 3 = 1\), and the weights of all other edges are \(0\).