CF2237G Send GCDs

这是一个运行两次（通信）的交互式问题。 有两名玩家：Ja（鬼魂）和 Quack（鸭子）。该问题的评测机（也就是本题的交互器）会先与 Ja 进行交互，Ja 结束交互后，评测机会与 Quack 进行交互。需要注意，Ja 和 Quack 不能直接相互传递信息；两位玩家只能通过评测机收发信息。 在交互开始前，评测机会确定一个整数 $n$ 以及一个长度为 $n$ 的正整数数组 $a_1,a_2,…,a_n$。这两个数列在两位玩家中均保持一致。 Ja 会从评测机处接收到 $n$ 和一个长度为 $n$ 的正整数数组 $a_1,a_2,…,a_n$，其中 $a_i\le 10^6$。Ja 的目标是要把这个数组发送给 Quack。为此，Ja 可以选择一个整数 $k$，其中 $$ k \le \left\lceil \frac{10n}{9} \right\rceil + 150， $$ 然后构造一个长度为 $k$ 的正整数数组 $b_1,b_2,…,b_k$，其中 $b_i\le 10^6$，并将其发送给评测机。随后，评测机会把整数 $n$ 和 $k$ 发送给 Quack。Quack 最多可以向评测机询问 $180n+150$ 次如下格式的查询： - 选择任意两个整数 $i,j$（$1\le i,j\le k,\ i\ne j$），评测机会返回 $\mathrm{gcd}(b_i,b_j)$。 这里，$\gcd(x,y)$ 表示整数 $x$ 和 $y$ 的[最大公因数（GCD）](https://en.wikipedia.org/wiki/Greatest_common_divisor)。 需要注意，$a$ 和 $b$ 对于 Quack 来说都是隐藏的；Quack 只能通过上述查询间接获知信息。 Ja 的目标是保证 Quack 能还原出原始数组 $a$。你的任务是分别充当这两位玩家，设计出最佳的交互策略，从而让 Quack 能准确地还原出原数组 $a$。 **第一次运行** 你的程序会在每个测试点上被运行两次。第一次运行时，你需要扮演 Ja。 **输入** 输入的第一行包含字符串 first，用于让你的程序识别为“第一次运行”，要模拟 Ja 的行为。 第二行包含一个整数 $t$（$1\le t\le 100$），表示测试用例数。接下来给出每个测试用例的数据。 第 $i$ 个测试用例的第一行包含一个整数 $n$（$1\le n\le 10^3$），表示此测试的 $a$ 的长度。 第 $i$ 个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$（$1\le a_i\le 10^6$），为此测试用例的数组 $a$。 保证所有测试用例的 $n$ 之和不超过 $10^3$。 **输出** 对每个测试用例，首先输出一个整数 $k$（$1\le k\le \left\lceil \frac{10n}{9} \right\rceil + 150$），表示数组 $b$ 的长度。然后输出 $k$ 个整数 $b_1,b_2,…,b_k$（$1\le b_i\le 10^6$），表示 Ja 要发送给评测机的数组 $b$。此数组会用于第二次运行中的询问过程。 输出后直接处理下一个测试用例，或在所有测试用例结束后直接退出程序。 **第二次运行** 在第二次运行时，你需要扮演 Quack。 **输入** 输入的第一行包含字符串 second，用于让你的程序识别为“第二次运行”，要模拟 Quack 的行为。 第二行包含一个整数 $t$（$1\le t\le 100$），表示测试用例数。此数值和第一次运行一致。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1\le n\le 10^3$，$1\le k\le \left\lceil \frac{10n}{9} \right\rceil + 150$），表示数组 $a$ 和 $b$ 的长度。 **注意第二次运行中的用例顺序可能会被打乱。请参见样例以获得更具体的说明。** **交互过程** 对于第 $i$ 个测试用例，你会收到 $n$ 和 $k$。随后你最多可以进行 $180n+150$ 次如下格式的查询： - ? i j（$1 \le i,j\le k,\ i\ne j$） 每次查询后，评测机会给出 $\mathrm{gcd}(b_i,b_j)$，你需从输入流中读取答案。 如果你的程序查询次数超过 $180n+150$ 次，应立即终止程序，并会收到 Wrong Answer 判罚。否则，程序可能继续读取已关闭的输入流，可能导致未知判罚。 当你认为自己已还原出原始数组 $a$ 时，需按格式输出： - ! $a_1,a_2,…,a_n$（$1\le a_i\le 10^6$） 随后你要么进入下一个测试用例，要么（如已做完全部测试用例）终止程序。 交互期间每次输出后请勿忘记换行并刷新输出流，否则会导致 Idleness limit exceeded 判罚。 如果在交互过程中读取到 $-1$，表示当前数据无效，应立即退出程序。这通常代表你的查询格式或次数有误，未及时退出会导致未知的判罚。 *刷新输出流的方法*： - C++ 可用 fflush(stdout) 或 cout.flush()； - Python 用 sys.stdout.flush()； - 其它语言参见相关文档。

无

无

在第一次运行时，共有两个测试用例。 对于第一个测试用例，Ja 得到 $a=[1,1,4,5,1,4]$，他选择发送 $b=[20,1,1,4,5,1,4]$。 对于第二个测试用例，Ja 得到 $a=[2,6,10]$，他选择发送 $b=[30,2,6,10]$。 在第二次运行时，测试用例顺序被打乱。例如，Quack 先收到了 $n=3$ 且 $k=4$ 的测试用例。他依次询问 $\mathrm{gcd}(b_1, b_i)$，其中 $i=2,3,4$，评测机依次回答 $2,6,10$，于是 Quack 成功还原了原数组 $[2,6,10]$。 然后 Quack 收到 $n=6$ 且 $k=7$ 的测试用例，同样询问 $\mathrm{gcd}(b_1, b_i)$，其中 $i=2,3,4,5,6,7$，评测机依次回答 $1,1,4,5,1,4$，从而还原出 $[1,1,4,5,1,4]$。 这个例子说明，即便第二次运行中各测试用例的顺序可能被打乱，实际使用的 $a$ 和 $b$ 数组都与第一次运行时相同。 由 ChatGPT 5 翻译