← 返回题目列表

Codeforces · 2081/D

D. 模图中的 MST

中文机器翻译题面 查看原题

给您一个包含 $$$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$$$。