Xor-quiz

题面翻译

本题是一道交互题。

交互库会随机生成一个集合 $A$，满足其中每个元素都是 $[1,c]$ 的正整数。$A$ 会在所有可能的情形里等概率地选取。接着令 $n=|A|$。$n,c$ 是公开情报。对每个正整数 $x\in [1,c]$，定义 $F(A,x)$ 表示 $A$ 中所有和 $x$ 互质的数的异或和。

现在你可以提出不超过 $\lceil 0.65c\rceil$ 个问题，每个问题的形式都必须如下：给定正整数 $x$，询问 $F(A,x)$ 的值。交互库在收到你的所有询问后，会一次性返回所有 $F(A,x)$ 的值。

你需要构造一个大小为 $n$、各元素均为 $[1,c]$ 间正整数的集合 $A'$，满足对全部的 $x\in [1,c]$ 都有 $F(A,x)=F(A',x)$。保证一定有解。

交互格式

你需要先读入两个正整数 $c,n(100\leq c\leq 10^6,0\leq n\leq c)$，含义如上。

接下来你需要输出一行一个整数 $q(0\leq q\leq \lceil 0.65c\rceil)$，表示你提出的问题数量。接下来一行输出 $q$ 个用空格隔开的正整数 $x_1,...,x_q(1\leq x_i\leq c)$，表示你提出的各个问题。

在你提出所有 $q$ 个问题后，交互库一次性给出全部问题的答案，你可以在输入中读入它们。

最后你需要输出 $n$ 个用空格隔开的互不相同的正整数 $A'_1,...,A'_n$，表示你找到的集合 $A'$ 中的各元素。

题目描述

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.

输入格式

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

输出格式

In the first line you should print an integer $q$ $(0 \le q \le \lceil 0.65 \cdot c \rceil)$ — the number of queries you want to ask. After that in the same line print $q$ integers $x_1, x_2, \ldots, x_q$ $(1 \le x_i \le c)$ — the queries.

For these queries you should read $q$ integers, $i$ -th of them is the answer to the described query for $x = x_i$ .

After that you should print $n$ distinct integers $A'_1, A'_2, \ldots, A'_n$ — the set $A'$ you found.

If there are different sets $A'$ that have the same answers for all possible queries, print any of them.

If you will ask more than $\lceil 0.65 \cdot c \rceil$ queries or if the queries will be invalid, the interactor will terminate immediately and your program will receive verdict Wrong Answer.

After printing the queries and answers do not forget to output end of line and flush the output buffer. Otherwise, you will get the Idleness limit exceeded verdict. To do flush use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• Read documentation for other languages.

Hacks

You cannot make hacks in this problem.

样例 #1

样例输入 #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

提示

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} $