GCD Guess

题目大意

交互题，猜一个数\(x(1\le x \le 10^9)\)。 每次可以输出一个\((? ,a, b)\),可以得到\(gcd(x + a, x + b)\)。 通过不超过\(30\)次询问来确定\(x\)。 题目链接

思路

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

假设有两个数\(a = (....000)_2\),即二进制以3个零结尾，那么\(gcd(a, 2^3) = 2^3\)。而假如\(a = (...100)_2\)，那么\(gcd(a, 2^3) \not = {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...n\)位均为\(0\)，那么不论高位是什么，gcd就是\(2^{n+1}\)，如果第\(n\)位是\(0\)，不会产生进位，那么\(gcd\)就不可能是\(2^{n+1}\)。

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

\(gcd(x + (1 << (i - 1)) - r, (1 << i) + x + (1 << (i - 1)) - r)= gcd(x + (1 << (i - 1)) - r, 1 << 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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/04/16/cf1665D/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！