← 返回题目列表

Codeforces · 2034/H

H. 拉扬 vs 拉亚内

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

Rayan 做出了最后的努力,声称自己比 Rayaneh(即波斯语中的计算机)更强大,以赢得 Reyhaneh 的心。为了验证这一点,雷哈内向花剌子米寻求帮助。 Khwarizmi 解释说,如果集合中没有元素可以写成其他元素的整数线性组合,则集合是整数线性无关的。每次给 Rayan 一组整数,并且必须识别最大可能整数线性独立子集之一。

请注意,单个元素始终被视为整数线性独立子集。

$$$a_1, \ldots, a_k$$$ 的整数线性组合是 $$$c_1 \cdot a_1 + c_2 \cdot a_2 + \ldots + c_k \cdot a_k$$$ 形式的任意和,其中 $$$c_1, \ldots, \ldots, c_k$$$ 是整数(可以是零、正数或负)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$),测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$),即集合的大小。第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^6$$$。

输出

在每个测试用例的第一行打印最大整数线性独立子集的大小。

在下一行中,以任意顺序打印一个此类子集。如果有多个有效子集,则打印其中任何一个。

示例

输入 #1

3
5
2 4 6 8 10
5
12 15 21 30 35
3
2 3 6

输出 #1

2
4 6
3
35 21 30
2
2 3

注意

在示例 1 中,$$$\{4, 6\}$$$ 是整数线性无关子集。可以证明不存在至少有$$$3$$$个元素的整数线性无关子集。

在示例 2 中,$$$\{35, 21, 30\}$$$ 是整数线性独立子集,因为任何两个元素的整数线性组合都不能创建第三个。不存在至少具有 $$$4$$$ 元素的整数线性独立子集。

在示例 3 中,$$$\{2, 3, 6\}$$$ 不是整数线性独立子集,因为 $$$6$$$ 可以写为 $$$6 \cdot 2 + (-2) \cdot 3$$$,它是 $$$\{2, 3\}$$$ 的整数线性组合。