← 返回题目列表

Codeforces · 1583/A

A. 风花颂

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

一把装饰着无名花朵的蝴蝶结,承载着同样无名之人的殷切希望。

你已经获得了被称为风花颂歌的优雅弓。武器上刻有一个 $$$n$$$ ($$$n \ge 3$$$) 正不同整数的数组(即不同,不允许重复)。

找到该数组的最大子集(即具有最大元素数),使其总和为合数。如果存在正整数 $$$y$$$ 使得 $$$1 < y < x$$$ 且 $$$x$$$ 可被 $$$y$$$ 整除,则正整数 $$$x$$$ 称为合数。

如果存在多个具有此最大大小的子集以及复合和,则可以输出其中任何一个。可以证明,在问题的约束下,这样的非空子集总是存在的。

输入

每个测试由多个测试用例组成。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 100$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 不同的整数 $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$1 \leq a_{i} \leq 200$$$) - 数组的元素。

输出

每个测试用例应该有两行输出。

第一行应包含一个整数 $$$x$$$:具有复合总和的最大子集的大小。下一行应包含 $$$x$$$ 空格分隔的整数,表示初始数组子集的索引。

示例

输入 #1

4
3
8 1 2
4
6 9 4 2
9
1 2 3 4 5 6 7 8 9
3
200 199 198

输出 #1

2
2 1
4
2 1 4 3
9
6 9 1 2 3 4 5 7 8
3
1 2 3

注意

在第一个测试用例中,子集 $$$\{a_2, a_1\}$$$ 的总和为 $$$9$$$,这是一个合数。 $$$3$$$ 大小的唯一子集的素数和等于 $$$11$$$。请注意,您还可以选择子集 $$$\{a_1, a_3\}$$$,总和为 $$$8 + 2 = 10$$$,它是合数,因为它可被 $$$2$$$ 整除。

在第二个测试用例中,所有元素的总和等于 $$$21$$$,这是一个合数。这里我们简单地将整个数组作为我们的子集。