这是一个交互问题。
给你两个整数 $$$c$$$ 和 $$$n$$$。陪审团有一个随机生成的集合 $$$A$$$,由不大于 $$$c$$$ 的不同正整数组成(它是从所有此类可能的集合以相等的概率生成的)。 $$$A$$$ 的大小等于$$$n$$$。
你的任务是猜测集合$$$A$$$。为了猜测它,您最多可以询问 $$$\lceil 0.65 \cdot c \rceil$$$ 查询。
在每个查询中,您选择一个整数 $$$1 \le x \le c$$$。作为此查询的答案,您将得到所有 $$$y$$$ 的按位异或和,使得 $$$y \in A$$$ 和 $$$gcd(x, y) = 1$$$ (即 $$$x$$$ 和 $$$y$$$ 互质)。如果不存在这样的$$$y$$$,则该异或和等于$$$0$$$。
您可以在开始时提出所有疑问,您将收到所有疑问的答案。之后,您将无法提出疑问。
您应该找到任何集合$$$A'$$$,使得$$$|A'| = n$$$ 和 $$$A'$$$ 和 $$$A$$$ 对于所有 $$$c$$$ 可能的查询具有相同的答案。
输入
首先给你两个整数 $$$c$$$ 和 $$$n$$$ ($$$100 \le c \le 10^6$$$, $$$0 \le n \le c$$$)。
互动
在第一行中,您应该打印一个整数 $$$q$$$ $$$(0 \le q \le \lceil 0.65 \cdot c \rceil)$$$ - 您要询问的查询数。之后在同一行中打印 $$$q$$$ 整数 $$$x_1, x_2, \ldots, x_q$$$ $$$(1 \le x_i \le c)$$$ - 查询。
对于这些查询,您应该读取 $$$q$$$ 整数,其中 $$$i$$$ 是所描述的 $$$x = x_i$$$ 查询的答案。
之后,您应该打印 $$$n$$$ 不同的整数 $$$A'_1, A'_2, \ldots, A'_n$$$ - 您找到的集合 $$$A'$$$。
如果存在不同的集合 $$$A'$$$ 对于所有可能的查询具有相同的答案,则打印其中的任何一个。
如果您询问超过 $$$\lceil 0.65 \cdot c \rceil$$$ 查询,或者查询无效,交互器将立即终止,您的程序将收到错误答案的判决。
打印查询和答案后,不要忘记输出行尾并刷新输出缓冲区。否则,您将得到超出空闲限制的判决。要进行冲洗,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 阅读其他语言的文档。
黑客
你无法解决这个问题。
示例
输入 #1
10 6 1 4 2 11 4 4 4
输出 #1
7 10 2 3 5 7 1 6 1 4 5 6 8 10
注意
该示例仅供您了解交互协议。您的解决方案不会在样品上进行测试。
在示例中 $$$A = \{1, 4, 5, 6, 8, 10\}$$$。进行了$$$7$$$查询,$$$7 \le \lceil 0.65 \cdot 10 \rceil = 7$$$,因此没有超出查询限制。
问题解答:
- 对于 $$$10$$$:$$$1$$$ 是 $$$A$$$ 集合中唯一与 $$$10$$$ 互质的数字,所以答案是 $$$1$$$
- 对于 $$$2$$$:$$$1_{10} \oplus 5_{10} = 001_2 \oplus 101_2 = 4_{10}$$$,其中 $$$\oplus$$$ 是按位异或
- 对于 $$$3$$$:$$$1_{10} \oplus 4_{10} \oplus 5_{10} \oplus 8_{10} \oplus 10_{10} = 0001_2 \oplus 0100_2 \oplus 0101_2 \oplus 1000_2 \oplus 1010_2 = 2_{10}$$$
- 对于 $$$5$$$:$$$1_{10} \oplus 4_{10} \oplus 6_{10} \oplus 8_{10} = 0001_2 \oplus 0100_2 \oplus 0110_2 \oplus 1000_2 = 11_{10}$$$
- 对于 $$$7$$$:$$$1_{10} \oplus 4_{10} \oplus 5_{10} \oplus 6_{10} \oplus 8_{10} \oplus 10_{10} = 0001_2 \oplus 0100_2 \oplus 0101_2 \oplus 0110_2 \oplus 1000_2 \oplus 1010_2 = 4_{10}$$$
- 对于 $$$1$$$:$$$1_{10} \oplus 4_{10} \oplus 5_{10} \oplus 6_{10} \oplus 8_{10} \oplus 10_{10} = 0001_2 \oplus 0100_2 \oplus 0101_2 \oplus 0110_2 \oplus 1000_2 \oplus 1010_2 = 4_{10}$$$
- 对于 $$$6$$$:$$$1_{10} \oplus 5_{10} = 0001_2 \oplus 0101_2 = 4_{10}$$$