← 返回题目列表

Codeforces · 2156/C

C. 白板上的最大 GCD

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

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

  • 擦除:从白板上选择一个整数并将其删除。该操作最多可以执行 $$$k$$$ 次。
  • 分裂:从白板上选择一个整数 $$$x\ge 3$$$。将其拆分为三个正整数 $$$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$$$ 的

的 美女 被定义为 $$$b$$$ 中所有元素的最大公约数。形式上,它是最大整数 $$$d$$$,使得 $$$d$$$ 可以除以 $$$x$$$ 作为 $$$b$$$ 元素的每个 $$$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$$$。

输出

对于每个测试用例,输出一个整数,表示执行操作后写在白板上的元素的最大美感。

示例

输入
复制

6
9 1
4 9 6 8 2 6 7 8 2
10 1
4 9 6 8 2 6 7 8 2 7
7 5
1 1 2 3 4 5 5
7 4
1 1 2 3 4 5 5
14 3
14 12 7 12 9 9 12 4 3 1 3 6 9 13
1 0
1

输出
复制

2
1
5
1
3
1

注意

在第一个测试用例中,您可以执行以下操作序列:

  • 擦除 $$$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$$$ 了。

在第二个测试用例中,请注意 擦除 操作只能删除一次出现的整数,即使存在重复项也是如此。在这里,我们只能删除一份$$$7$$$,所以白板上还剩下一份$$$7$$$。因此,我们无法执行与第一个测试用例中相同的操作序列。

在第三个测试用例中,我们可以擦除整数 $$$1$$$、$$$1$$$、$$$2$$$、$$$3$$$ 和 $$$4$$$,只在白板上留下 $$$[5, 5]$$$。由于两个数字都是 $$$5$$$,因此它们的最大公约数是 $$$5$$$,最大美度是 $$$5$$$。