codeforces#P2081D. MST in Modulo Graph
MST in Modulo Graph
Description
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.
Input
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$.
Output
For each test case, output a single integer — the weight of the minimum spanning tree.
4
5
4 3 3 4 4
10
2 10 3 2 9 9 4 6 4 6
12
33 56 48 41 89 73 99 150 55 100 111 130
7
11 45 14 19 19 8 10
1
0
44
10
Note
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$.