CF1806F1 GCD Master (easy version)

这是该问题的简单版本。两个版本的唯一区别在于 $m$ 的约束条件。只有当你同时解决了两个版本的问题后，才能进行 Hack。 给定一个长度为 $n$ 的数组 $a$，以及两个整数 $m$ 和 $k$。数组 $a$ 中的每个元素都满足 $1 \le a_i \le m$。 每次操作，你可以选择两个下标 $i$ 和 $j$，满足 $1 \le i < j \le |a|$，然后将 $\gcd(a_i, a_j)$ 添加到数组末尾，并从数组中删除 $a_i$ 和 $a_j$。注意，每次操作后数组长度减少 $1$。 请你在恰好进行 $k$ 次操作后，求出数组元素和的最大可能值。

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 10^6$；$1 \le m \le 10^6$；$1 \le k \le n-1$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le m$）。 保证所有测试用例中 $n$ 的总和不超过 $10^6$，所有测试用例中 $m$ 的总和不超过 $10^6$。

对于每个测试用例，输出在最优操作下，进行 $k$ 次操作后数组元素和的最大可能值。

在第一个测试用例中，最优的方法是第一次操作选择 $i=1$，$j=3$。最终序列为 $[7,4]$。 由 ChatGPT 4.1 翻译