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

In the first test, the interaction proceeds as follows. SolutionJuryExplanation $ \texttt{2} $ There are 2 test cases. $ \texttt{2} $ In the first test case, the hidden permutation is $ [1,0] $ , with length $ 2 $ . $ \texttt{? 1 2} $ $ \texttt{1} $ The solution requests $ \gcd(p_1,p_2) $ , and the jury responds with $ 1 $ . $ \texttt{! 1 2} $ $ \texttt{1} $ The solution knows that either $ p_1=0 $ or $ p_2=0 $ , and prints the answer. Since the output is correct, the jury responds with $ 1 $ and continues to the next test case. $ \texttt{5} $ In the second test case, the hidden permutation is $ [2,4,0,1,3] $ , with length $ 5 $ . $ \texttt{? 1 2} $ $ \texttt{2} $ The solution requests $ \gcd(p_1,p_2) $ , and the jury responds with $ 2 $ . $ \texttt{? 2 3} $ $ \texttt{4} $ The solution requests $ \gcd(p_2,p_3) $ , and the jury responds with $ 4 $ . $ \texttt{! 3 3} $ $ \texttt{1} $ The solution has somehow determined that $ p_3=0 $ , and prints the answer. Since the output is correct, the jury responds with $ 1 $ .Note that the empty lines in the example input and output are for the sake of clarity, and do not occur in the real interaction. After each test case, make sure to read $ 1 $ or $ -1 $ .