Codeforces Round #781 (Div. 2)

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

思路

30 次询问，一开始想二分，但没找到单调性；
按位来判断，如果每次能判断 1 位也正好满足条件
如果已经求出了 x 的前 i - 1位，记为 r；对于第 i 位，\(\gcd(x-r,2^i)\) == \(2^i\) 则 x 的第 \(i\) 位是 0
但询问是 x 加一个数，不能询问 \(x-r\)；所以可以询问 \(\gcd(x-r+2^i,2^{i+1})==2^{i+1}\), 则 x 的第 i 位是 1
令 \(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

GCD + 位运算

题意

思路

最新文章

热门文章