题面
给定一个长度为 \(n\) 的排列 \(0, 1, \cdots, n - 1\)。可以进行最多 \(2n\) 次询问，每次询问给出两个下标 \(i, j\)，交互器会返回 \(\gcd(p_i, p_j)\)。询问以后，需要输出两个下标 \(x, y\)，满足 \(p_x = 0 \lor p_y = 0\)。特别地，\(\gcd(0, x) = x\)。
题解
观察次数限制，我们需要用不多于 \(2\) 次询问判断出一个数是否为 \(0\)，考虑到排列中元素互不相通的性质，所以有 \(p_k = 0 \Rightarrow \gcd(p_i, p_k) \neq \gcd(p_j, p_k)\)。转化一下，可以得出 \(\gcd(p_i, p_k) = \gcd(p_j, p_k) \Rightarrow p_k \neq 0\)，但是显然这种判断方法不能保证每 \(2\) 次询问便筛出一个元素。考虑在对于三个下标 \(a, b, c\)，获得了 \(\gcd(p_a, p_b), \gcd(p_a, p_c)\) 两个值的情况下，如何推导出更多信息。
发现 \(\gcd(p_a, p_b) \le x, \gcd(p_a, 0) = p_a\)，所以可以推出
\[\gcd(p_a, p_c) < \gcd(p_a, p_b) \Rightarrow p_c \neq 0
\]
证明考虑利用上述不等式推导
\[\gcd(p_a, p_c) < \gcd(p_a, p_b) \Rightarrow \gcd(p_a, p_c) < \gcd(p_a, p_b) \le p_a = \gcd(p_a, 0) \Rightarrow p_c \neq 0
\]
对称地，可以得出
\[\gcd(p_a, p_b) < \gcd(p_a, p_c) \Rightarrow p_b \neq 0
\]
综上，我们可以得出结论：
- \(\gcd(p_a, p_b) = \gcd(p_a, p_c) \Rightarrow a \neq 0\)
- \(\gcd(p_a, p_b) < \gcd(p_a, p_c) \Rightarrow p_b \neq 0\)
- \(\gcd(p_a, p_c) < \gcd(p_a, p_b) \Rightarrow p_c \neq 0\)
所以我们对于任意三个下标 \(a, b, c\)，询问出 \(\gcd(p_a, p_b), \gcd(p_a, p_c)\) 两个值，一定可以排除一个下标对应的元素，最多需要排除 \(n - 2\) 次。最多共询问 \(2\left(n - 2\right)\) 次，可以通过本题。
Code
//Codeforces - 1762D
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
int main() {
valueType T;
std::cin >> T;
for (int testcase = 0; testcase < T; ++testcase) {
valueType N;
std::cin >> N;
if (N == 2) {
std::cout << "! 1 2" << std::endl;
valueType result;
std::cin >> result;
if (result == -1)
return 0;
continue;
}
ValueVector source(N);
std::iota(source.begin(), source.end(), 1);
while (source.size() >= 3) {
std::cout << "? " << source[0] << ' ' << source[1] << std::endl;
valueType result_0_1;
std::cin >> result_0_1;
std::cout << "? " << source[0] << ' ' << source[2] << std::endl;
valueType result_0_2;
std::cin >> result_0_2;
if (result_0_1 == result_0_2) {
source.erase(source.begin());
} else if(result_0_1 > result_0_2) {
source.erase(source.begin() + 2);
} else {
source.erase(source.begin() + 1);
}
}
std::cout << "! " << source.front() << ' ' << source.back() << std::endl;
valueType result;
std::cin >> result;
if (result == -1)
return 0;
}
return 0;
}