CF2081D.MST in Modulo Graph

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

输出格式

对于每个测试用例，输出一个整数表示最小生成树的总权重。

输入输出样例

输入#1

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

说明/提示

第一个测试用例中，一种可能的连接方式是选择边 $(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$ 。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页