CF2156C.Maximum GCD on Whiteboard

给定一个整数 $k$，以及 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 写在白板上，其中 $1 \le a_i \le \boldsymbol{n}$。你可以进行以下操作：

• 擦除（Erase）：任选白板上的一个整数，将其擦除。该操作最多可以执行 $k$ 次。
• 分裂（Split）：从白板上选择一个满足 $x\ge 3$ 的整数 $x$，将其分裂为 $x_1$、$x_2$ 和 $x_3$，使得 $x_1 + x_2 + x_3 = x$，且 $1 \le x_1 \le x_2 \le x_3$。然后将 $x$ 从白板上擦除，并将 $x_1$ 和 $x_3$ 写到白板上（$x_2$ 被丢弃，不会写到白板上）。该操作可以执行任意次数。

一组整数 $b$ 的美丽值（beauty）定义为 $b$ 中所有元素的最大公约数。即最大的整数 $d$，使得对于 $b$ 中的每个元素 $x$，都有 $d$ 整除 $x$。

你的任务是，在执行不超过 $k$ 次擦除操作和任意次分裂操作后，求白板上可能剩下整数的最大美丽值。

每个测试用例包含若干组数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数。

每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le k \le n-1$），分别表示白板上的整数数量和允许执行擦除操作的最多次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le \boldsymbol{n}$），表示白板上最初写下的整数。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出一个整数，表示在操作后白板上剩余整数的最大美丽值。

在第一个测试用例中，你可以按以下顺序操作：

• 擦除 $7$。白板上剩余整数为 $[4,9,6,8,2,6,8,2]$。
• 将 $9$ 分裂为 $2$、$3$、$4$。$9$ 被擦除，新增 $2$ 和 $4$。白板上变为 $[4,\underline{2,4},6,8,2,6,8,2]$。
• 将 $8$ 分裂为 $2$、$2$、$4$。$8$ 被擦除，新增 $2$ 和 $4$。白板上变为 $[4,2,4,6,\underline{2,4},2,6,8,2]$（分裂哪一个 $8$ 没有关系，元素顺序也无关紧要）。

最终白板上整数的美丽值为 $2$，即为这些数的最大公约数（$2$、$4$、$6$、$8$均能被 $2$ 整除）。注意最后一步分裂操作不是必要的，第二步结束后美丽值就已经是 $2$。

在第二个测试用例中，注意擦除操作只能删除某个数的一次出现，如果有多个同样的数，只能擦除其中一个。所以即使擦除了一个 $7$，白板上还剩余一个 $7$，无法像第一个样例那样继续操作。

在第三个测试用例中，可以擦除 $1$、$1$、$2$、$3$ 和 $4$，只剩 $[5, 5]$。这两个数的最大公约数是 $5$，最大美丽值为 $5$。

由 ChatGPT 5 翻译