2100

GCD Queries

出处：CF1762D

题目大意：交互题，给定一个秘密的 $[0,n-1]$ 排列 $p$ ，请在至多 $2n$ 次询问下，找出 $p_x$ 和 $p_y$ 其中，至少有一个位置为 $0$ ，每次询问给出 $i,j$ ，返回 $gcd(i,j)$ 。

数据范围： $2 \leq n \leq 2 \cdot 10^4$ 。

思路：这道题其实跟CF1634D 非常相似，思路都是动态更新当前可能的解。

于是，这里考虑每次判断三个数，要排除掉一个必然不是0的数，于是如何排除？

考虑当前的数为 $a,b,c$ ，查询 $gcd(a,b)$ 和 $gcd(a,c)$ 。

若 $gcd(a,b)=gcd(a,c)$ ，那么 $a$ 必然不是 $0$ 。

若 $gcd(a,b)>gcd(a,c)$ ，那么 $c$ 必然不是 $0$ ，可以使用反证法证明。

若 $gcd(a,b)<gcd(a,c)$ ，那么 $b$ 必然不是 $0$ ，可以使用反证法证明。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


int ask(int l, int r) {
    cout << "? " << l << ' ' << r << '\n';
    cout.flush();
    int op;
    cin >> op;
    return op;
}
void report(ll sum, ll sum2) {
    cout << "! " << sum << ' ' << sum2 << '\n';
    cout.flush();
    int op;
    cin >> op;
    if (op == 1)
        return;
    else
        exit(0);
}
void solve() {
    int n;
    cin >> n;
    pii ans = make_pair(1, 2);
    auto upd = [&](int x) -> void {
        int op1 = ask(ans.first, x);
        int op2 = ask(ans.second, x);
        if (op1 == op2)
            ans = make_pair(ans.first, ans.second);
        else if (op1 > op2)
            ans = make_pair(ans.first, x);
        else
            ans = make_pair(ans.second, x);
    };
    rep(i, 3, n) { upd(i); }
    report(ans.first, ans.second);
    return;
}