• 欢迎光临~

Codeforces Round #781 (Div. 2) - D. GCD Guess

开发技术 开发技术 2022-10-17 次浏览

GCD + 位运算

[Problem - 1665D - Codeforces](https://codeforces.com/problemset/problem/1627/D)

题意

交互题,有一个未知数 (x;(1<=x<=10^9)), 最多有 30 次询问,每次询问给出 (1<=a,b<=10^9), 返回 (gcd(a+x,b+x)), 求出 x

思路

  1. 30 次询问,一开始想二分,但没找到单调性;
  2. 按位来判断,如果每次能判断 1 位也正好满足条件
  3. 如果已经求出了 x 的前 i - 1位,记为 r;对于第 i 位,(gcd(x-r,2^i)) == (2^i) 则 x 的第 (i) 位是 0
  4. 但询问是 x 加一个数,不能询问 (x-r);所以可以询问 (gcd(x-r+2^i,2^{i+1})==2^{i+1}), 则 x 的第 i 位是 1
  5. (a=2^i-r,;b=-r+2^i+2^{i+1}) 即可
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
#define endl "n"

typedef long long ll;
typedef pair<int, int> PII;
int y;

void query(int a, int b)
{
	cout << "? " << a << " " << b << endl;
	cout.flush();
	cin >> y;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		int r = 0;
		for (int i = 0; i < 30; i++)
		{
			int a = (1 << i) - r;
			int b = a + (1 << i + 1);
			query(a, b);
			if (y == (1 << i + 1))
				r |= (1 << i);
		}
		cout << "! " << r << endl;
		cout.flush();
	}
    return 0;
}
程序员灯塔
转载请注明原文链接:Codeforces Round #781 (Div. 2) - D. GCD Guess
喜欢 (0)