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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ . Note that $ \gcd(x,0)=\gcd(0,x)=x $ for all positive integers $ 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 $ .

输出格式

The interaction for each test case begins by reading the integer $ n $ . To make a query, output "? $ i $ $ j $ " ( $ 1 \leq i, j \leq n $ , $ i \neq j $ ) without quotes. Afterwards, you should read a single integer — the answer to your query $ \gcd(p_i,p_j) $ . You can make at most $ 2n $ such queries in each test case. If you want to print the answer, output "! $ x $ $ y $ " ( $ 1 \leq x, y \leq n $ ) without quotes. After doing that, read $ 1 $ or $ -1 $ . If $ p_x=0 $ or $ p_y=0 $ , you'll receive $ 1 $ , otherwise you'll receive $ -1 $ . If you receive $ -1 $ , your program must terminate immediately to receive a Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream. If you receive the integer $ -1 $ instead of an answer or a valid value of $ n $ , it means your program has made an invalid query, has exceeded the limit of queries, or has given an incorrect answer on the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream. After printing a query or the answer, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. Hacks To hack, use the following format. The first line should contain a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ). The first line of each test case should contain a single integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^4 $ ). The second line of each test case should contain $ n $ space separated integers $ p_1,p_2,\ldots,p_n $ . $ p $ should be a permutation of $ [0,1,2,\ldots,n-1] $ . The sum of $ n $ should not exceed $ 2 \cdot 10^4 $ .

输入输出样例

输入样例 #1

2
2

1

1
5

2

4

1

输出样例 #1

? 1 2

! 1 2


? 1 2

? 2 3

! 3 3

说明

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

**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) $ 的值。

注意，排列 $ p $ 在进行任何查询之前就已经固定，并且不依赖于查询。

$ \gcd(x, y) $ 表示整数 $ x $ 和 $ y $ 的[最大公约数 (GCD)](https://en.wikipedia.org/wiki/Greatest**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) $ 的值。 注意，排列 $ p $ 在进行任何查询之前就已经固定，并且不依赖于查询。 $ \gcd(x, y) $ 表示整数 $ x $ 和 $ y $ 的[最大公约数 (GCD)](https://en.wikipedia.org/wiki/Greatest