CF1566H.Xor-quiz

This is an interactive problem.

You are given two integers $c$ and $n$. The jury has a randomly generated set $A$ of distinct positive integers not greater than $c$ (it is generated from all such possible sets with equal probability). The size of $A$ is equal to $n$.

Your task is to guess the set $A$. In order to guess it, you can ask at most $\lceil 0.65 \cdot c \rceil$ queries.

In each query, you choose a single integer $1 \le x \le c$. As the answer to this query you will be given the bitwise xor sum of all $y$, such that $y \in A$ and $gcd(x, y) = 1$ (i.e. $x$ and $y$ are coprime). If there is no such $y$ this xor sum is equal to $0$.

You can ask all queries at the beginning and you will receive the answers to all your queries. After that, you won't have the possibility to ask queries.

You should find any set $A'$, such that $|A'| = n$ and $A'$ and $A$ have the same answers for all $c$ possible queries.

这是一个交互式问题。

你将获得两个整数 $c$ 和 $n$。评测系统持有一个随机生成的集合 $A$，其中包含 $n$ 个互不相同的正整数，且每个元素均不超过 $c$（该集合在所有满足条件的可能集合中等概率随机生成）。

你的任务是猜出集合 $A$。为此，你最多可以进行 $\lceil 0.65 \cdot c \rceil$ 次查询。

每次查询中，你选择一个整数 $1 \le x \le c$。作为对该查询的响应，你将得到所有满足 $y \in A$ 且 $\gcd(x, y) = 1$（即 $x$ 与 $y$ 互质）的 $y$ 的按位异或和（bitwise xor sum）。若不存在这样的 $y$，则该异或和为 $0$。

你必须在开始时一次性提交全部查询，随后将立即收到所有查询的响应结果；此后你将无法再提出任何查询。

你需要找出任意一个集合 $A'$，满足 $|A'| = n$，且对全部 $c$ 个可能的查询（即对每个 $x \in \{1,2,\dots,c\}$）而言，$A'$ 与 $A$ 给出的响应完全相同。

Firstly you are given two integers $c$ and $n$ ($100 \le c \le 10^6$, $0 \le n \le c$).

首先给你两个整数 $c$ 和 $n$（$100 \le c \le 10^6$，$0 \le n \le c$）。

The sample is made only for you to understand the interaction protocol. Your solution will not be tested on the sample.

In the sample $A = {1, 4, 5, 6, 8, 10}$. $7$ queries are made, $7 \le \lceil 0.65 \cdot 10 \rceil = 7$, so the query limit is not exceeded.

Answers for the queries:

• For $10$: $1$ is the only number in the set $A$ coprime with $10$, so the answer is $1$
• For $2$: $1_{10} \oplus 5_{10} = 001_2 \oplus 101_2 = 4_{10}$, where $\oplus$ is the bitwise xor
• For $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}$
• For $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}$
• For $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}$
• For $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}$
• For $6$: $1_{10} \oplus 5_{10} = 0001_2 \oplus 0101_2 = 4_{10}$

该样例仅用于帮助你理解交互协议。你的解决方案不会在该样例上进行测试。

在该样例中，$A = \{1, 4, 5, 6, 8, 10\}$。共进行了 $7$ 次查询，而 $7 \le \lceil 0.65 \cdot 10 \rceil = 7$，因此未超出查询次数限制。

各查询的答案如下：

• 对于 $10$：集合 $A$ 中唯一与 $10$ 互质的数是 $1$，因此答案为 $1$；
• 对于 $2$：$1_{10} \oplus 5_{10} = 001_2 \oplus 101_2 = 4_{10}$，其中 $\oplus$ 表示按位异或（bitwise xor）；
• 对于 $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}$。