题解：CF1665D GCD Guess

由数据范围不难想到按位考虑，所以我们尽量把每次询问凑成 $2$ 的幂次相关的数。

在二进制条件下，设最低位为第 $0$ 位。目前要猜测第 $i$ 位的值，设 $t$ 表示前 $i - 1$ 位所贡献的值。令 $a < b$，则有（加粗表示第 $i$ 位）：

由公式 $\gcd (t + a,t + b) = \gcd (t + a,b - a)$ 可知（加粗表示第 $i$ 位）：

此时 $\gcd (t + a,b - a) = 2^i$。当实际 $x$ 的第 $i$ 位为 $1$ 时，会产生 $2$ 次进位，使得 $\gcd (t’ + a,b - a) = 2^{i + 1}$。因此可以得到以下代码：

1
2
3
4
5

for (int i = 0;i < 30;++i)//猜测第 i 位 
{
    int ans = query ((1 << i) - x,(1 << i) + (1 << (i + 1)) - x);
    if (ans == 1 << (i + 1)) x |= 1 << i;
}