CF1762D.GCD Queries

This is an interactive problem.

There is a secret permutation $p$ of $[0,1,2,\ldots,n-1]$. Your task is to find $2$ indices $x$ and $y$ ($1 \leq x, y \leq n$, possibly $x=y$) such that $p_x=0$ or $p_y=0$. In order to find it, you are allowed to ask at most $2n$ queries.

In one query, you give two integers $i$ and $j$ ($1 \leq i, j \leq n$, $i \neq j$) and receive the value of $\gcd(p_i,p_j)^\dagger$.

Note that the permutation $p$ is fixed before any queries are made and does not depend on the queries.

$^\dagger$ $\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$. Note that $\gcd(x,0)=\gcd(0,x)=x$ for all positive integers $x$.

这是一个交互式问题。

存在一个 $[0,1,2,\ldots,n-1]$ 的秘密排列 $p$。你的任务是找出两个下标 $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$ 的最大公约数（GCD）。注意对所有正整数 $x$，均有 $\gcd(x,0)=\gcd(0,x)=x$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^4$).

After reading the integer $n$ for each test case, you should begin the interaction.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^4$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^4$）。

对每个测试用例读入整数 $n$ 后，你应开始交互。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^4$。

In the first test, the interaction proceeds as follows.

Solution

Jury

Explanation

$\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$.

在第一个测试用例中，交互过程如下所示。

解法

出题人

解释

$\texttt{2}$

共有 2 个测试用例。

$\texttt{2}$

在第一个测试用例中，隐藏的排列为 $[1,0]$，长度为 $2$。

$\texttt{? 1 2}$

$\texttt{1}$

解法请求 $\gcd(p_1,p_2)$，出题人返回 $1$。

$\texttt{! 1 2}$

$\texttt{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$。