题意
有个长度为n的排列p，[0,1,2,...n-1]，你可以进行至多2*n次询问，每次询问两个i，j，返回gcd(pi,pj)，让你在规定时间内猜出0在哪两个位置之一
思路
这是一道交互题，询问的上限是2n次
通过三个数，可以去除掉一个不是0的数
对三个数进行以下询问，gcd(a,i),gcd(b,i)
如果gcd(a,i) != gcd(b,i)，那么其中a，b小的被i取代，因为a，b中假如有0，那么一定是大的数，那么小的数一定不是0
如果gcd(a,i) == gcd(b,i)，那么跳过i，因为假如i是0，因为数列每个数都不同，所必不可能相等
那么for一遍数组，每次和当前位置i进行两次询问，最多2n的限制内就可以筛选出0可能存在的位置p，q
代码
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e4 + 10;
int n, t = 1;
long long a[N], b[N];
int pw[N];
int l[N], cnt[N];
const int mod = 998244353;
map<int, int> mp;
int v[N];
int ask(int x, int y) {
cout << "? " << x << ' ' << y << endl;
int u;
cin >> u;
return u;
}
void ok(int x, int y) {
cout << "! " << x << ' ' << y << endl;
int u;
cin >> u;
}
void run() {
cin >> n;
int p = 1, q = 2;
for (int i = 3; i <= n; i++) {
int r1 = ask(p, i), r2 = ask(q, i);
if (r1 < r2) {
p = i;
}
if (r1 > r2) {
q = i;
}
}
ok(q, p);
}
int main() {
srand(time(0));
cin >> t;
while (t--)
run();
return 0;
}
