CF1762D GCD Queries

这是一个交互题。 有一个长度为 $n$ 的秘密排列 $p$，它是 $[0,1,2,\ldots,n-1]$ 的一个排列。你的任务是找到两个下标 $x$ 和 $y$（$1 \leq x, y \leq n$，允许 $x=y$），使得 $p_x=0$ 或 $p_y=0$。为此，你最多可以进行 $2n$ 次询问。 每次询问，你可以给出两个整数 $i$ 和 $j$（$1 \leq i, j \leq n$，且 $i \neq j$），你将会得到 $\gcd(p_i,p_j)^\dagger$ 的值。 注意，排列 $p$ 在所有询问开始前就已经确定，并且不会因为你的询问而改变。 $^\dagger$ $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。注意，对于所有正整数 $x$，都有 $\gcd(x,0)=\gcd(0,x)=x$。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试数据组数。每组测试数据描述如下。 每组测试数据的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^4$）。 读入每组测试数据的 $n$ 后，你应当开始与评测机交互。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^4$。

每组测试数据的交互以读入整数 $n$ 开始。 每次询问，你需要输出 "? $i$ $j$"（$1 \leq i, j \leq n$，$i \neq j$），然后读入一个整数，表示本次询问的答案 $\gcd(p_i,p_j)$。每组测试数据最多可以进行 $2n$ 次询问。 如果你想输出答案，输出 "! $x$ $y$"（$1 \leq x, y \leq n$）。此后，你需要读入 $1$ 或 $-1$。如果 $p_x=0$ 或 $p_y=0$，你将收到 $1$，否则收到 $-1$。如果收到 $-1$，你的程序必须立即终止，否则会被判为 Wrong Answer。否则，你的程序可以继续运行，但会因为读取了关闭的流而得到任意判题结果。 如果你在任何时候读入了 $-1$（无论是答案还是 $n$），说明你的程序进行了非法操作、超出了询问次数限制，或上一组数据输出了错误答案。你的程序必须立即终止，否则会被判为 Wrong Answer。否则，你的程序可以继续运行，但会因为读取了关闭的流而得到任意判题结果。 每次输出询问或答案后，不要忘记输出换行并刷新输出缓冲区。否则会被判为 Idleness limit exceeded。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 Hack 时请使用如下格式： 第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）。 每组测试数据的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^4$）。 每组测试数据的第二行包含 $n$ 个用空格分隔的整数 $p_1,p_2,\ldots,p_n$。$p$ 必须是 $[0,1,2,\ldots,n-1]$ 的一个排列。 所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^4$。

在第一组测试中，交互过程如下： | 选手程序 | 交互库 | 说明 | |:-:|:-:|:-:| | | $\texttt{2}$ | 共有两组测试数据。 | | | $\texttt{2}$ | 在第一组测试数据中，隐藏的排列是 $[1,0]$，长度为 $2$。 | | $\texttt{? 1 2}$ | $\texttt{1}$ | 选手程序询问了 $\gcd(p_1,p_2)$，交互库返回了 $1$。 | | $\texttt{! 1 2}$ | $1$ | 选手程序知道了 $p_1=0$ 或 $p_2=0$，并输出了答案。因为答案是正确的，所以交互库返回了 $1$， 并进入下一组测试数据。 | | | $\texttt{5}$ | 在第二组测试数据中，隐藏的排列是 $[2,4,0,1,3]$，长度为 $5$。 | | $\texttt{? 1 2}$ | $\texttt{2}$ | 选手程序询问了 $\gcd(p_1,p_2)$，交互库返回了 $2$。 | | $\texttt{? 2 3}$ | $\texttt{4}$ | 选手程序询问了 $\gcd(p_2,p_3)$，交互库返回了 $4$。 | | $\texttt{! 3 3}$ | $\texttt{1}$ | 选手程序不知怎么就判断了 $p_3=0$，并输出了答案。因为答案是正确的，所以交互库返回了 $1$。 | 注意样例输入输出中的空行是为了便于清晰而添加的，真实的交互过程中没有空行。 **在每组测试数据后，务必读入 $1$ 或 $-1$。**