codeforces#P2081D. MST in Modulo Graph
MST in Modulo Graph
以下题面由 AI 翻译。
题目描述
给定一个包含 $n$ 个顶点的完全图，其中第 $i$ 个顶点的权重为 $p_i$。连接顶点 $x$ 和顶点 $y$ 的边的权重等于 $\operatorname{max}(p_x, p_y) \bmod \operatorname{min}(p_x, p_y)$。
求该图中连接所有 $n$ 个顶点的 $n - 1$ 条边的最小总权重。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。
每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)。
每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le 5 \cdot 10^5$)。
所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。
所有测试用例的 $\max(p_1,p_2,\ldots,p_n)$ 之和不超过 $5 \cdot 10^5$。
输出格式
对于每个测试用例，输出一个整数——最小生成树的权重。
样例数据
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
提示
在第一个测试用例中，一种可能的连接方式是选择边 $(1, 2)$、$(1, 4)$、$(1, 5)$ 和 $(2, 3)$。第一条边的权重为 $\operatorname{max}(p_1, p_2) \bmod \operatorname{min}(p_1, p_2)=4 \bmod 3 = 1$，其他边的权重均为 $0$。