CF1566H Xor-quiz

这是一个交互题。 你将得到两个整数 $c$ 和 $n$。评测器随机生成一个由不超过 $c$ 的不同正整数组成的集合 $A$（从所有可能的集合中等概率生成），集合 $A$ 的大小为 $n$。 你的任务是猜出集合 $A$。为此，你最多可以询问 $\lceil 0.65 \cdot c \rceil$ 次。 每次询问，你可以选择一个整数 $1 \le x \le c$。对于这个询问，你将得到所有满足 $y \in A$ 且 $\gcd(x, y) = 1$ 的 $y$ 的按位异或和（即 [bitwise xor sum](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)）。如果没有这样的 $y$，则异或和为 $0$。 你可以在一开始就提出所有的询问，并一次性获得所有询问的答案。之后你将无法再进行询问。 你需要找出任意一个集合 $A'$，使得 $|A'| = n$，并且对于所有 $c$ 个可能的询问，$A'$ 和 $A$ 的答案都相同。 如果存在多个满足条件的集合 $A'$，输出其中任意一个即可。 如果你询问次数超过 $\lceil 0.65 \cdot c \rceil$ 或者询问不合法，交互器会立即终止并判定你的程序为 Wrong Answer。 在输出询问和答案后，不要忘记输出换行并刷新输出缓冲区，否则会被判为 Idleness limit exceeded。刷新输出的方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 说明 本题不支持 Hack。

首先输入两个整数 $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'$，输出其中任意一个即可。

样例仅用于帮助你理解交互协议，评测时不会用到样例。 在样例中，$A = \{1, 4, 5, 6, 8, 10\}$。共进行了 $7$ 次询问，$7 \le \lceil 0.65 \cdot 10 \rceil = 7$，未超过询问上限。 各个询问的答案如下： - 对于 $10$：只有 $1$ 与 $10$ 互质且在 $A$ 中，所以答案为 $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}$。 由 ChatGPT 4.1 翻译