【Codeforces】1665D GCD Guess 题解

思路

不能超过30次，所以应该往位运算上靠 (反正我当时是没想到)

假设有两个数 $a = (\ldots000)_2$，即二进制以3个零结尾，那么 $\gcd(a, 2^3) = 2^3$。而假如 $a = (\ldots100)_2$，那么 $\gcd(a, 2^3) \neq 2^3$。

所以我们就借用这种思路。我们用 $r$ 表示我们已经得到的 $x$ 的低位部分。那么 $x - r$ 就是我们需要去判断的位数。

如何判断第 $n$ 位是不是 $1$？（此时低位部分已经被减去，均为 $0$），那么我们就让这一位加上 $1$，再求与 $2^{n+1}$ 的 gcd。如果结果是 $2^{n+1}$，那么第 $n$ 位就是 $1$。

因为如果第 $n$ 位是 $1$，再在这一位加上 $1$ 后，一定会产生进位。那么 $1, 2, 3, \ldots, n$ 位均为 $0$，那么不论高位是什么，gcd 就是 $2^{n+1}$。如果第 $n$ 位是 $0$，不会产生进位，那么 gcd 就不可能是 $2^{n+1}$。

而题目返回的值是 $\gcd(x+a, x+b)$ 的值，所以我们需要稍微转换一下。

$$\gcd(x + (1 \ll (i-1)) - r,\ (1 \ll i) + x + (1 \ll (i-1)) - r) = \gcd(x + (1 \ll (i-1)) - r,\ 1 \ll i)$$

代码

#include <cstdio>
#include <iostream>
using namespace std;

int query(int a, int b)
{
   cout << "? " << a << " " << a + b << endl;
   int tmp; cin >> tmp;
   return tmp;
}

int T;

int main()
{
    cin >> T;
    while(T--) {
        int r = 0;
        for(int i = 1; i <= 30; ++i) {
            int tmp = query((1 << (i - 1)) - r, 1 << i);
            if(tmp == (1 << i)) 
                r |= 1 << (i - 1);
        }
        cout << "!" << " " << r << endl;
    }
    return 0;
}