CF1513D GCD and MST

给定一个长度为 $n$（$n \geq 2$）的正整数数组 $a$ 和一个整数 $p$。考虑一个有 $n$ 个顶点的无向带权图，顶点编号从 $1$ 到 $n$，对于每一对顶点 $i$ 和 $j$（$i

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$（$2 \leq n \leq 2 \times 10^5$）和 $p$（$1 \leq p \leq 10^9$），分别表示节点数和参数 $p$。 第二行包含 $n$ 个整数 $a_1, a_2, a_3, \dots, a_n$（$1 \leq a_i \leq 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出 $t$ 行，每行一个整数，表示对应图的最小生成树的权值。

以下是样例的四个测试用例对应的图（可能的最小生成树的边用粉色标记）： 对于测试用例 1  对于测试用例 2  对于测试用例 3  对于测试用例 4  由 ChatGPT 4.1 翻译