Codeforces Round #781 D. GCD Guess

传送门

题目大意

交互题，每次询问给出 \(a,b\) ， 得到 \(gcd(x+a,x+b)(1\leq x\leq10^9,1\leq a,b\leq2\times10^9)\) ，\(30\) 次询问内求出 \(x\) 。

思路

考虑通过回答来确定 \(x\) 二进制上每一位的值，我们每次可以记录 \(0\) 到 \(i\) 位的答案为 \(ans_i\) ，查询 \(gcd(x-ans_i+2^{i+1},x - ans_i +2^{i+1}+2^{i+2})=gcd(x-ans_i+2^{i+1},2^{i+2})\) 来确定第 \(i+1\) 位的值，如果得到的回答 \(\neq 2^{i+2}\) ，那么第 \(i+1\) 位就为 \(1\) ，否则为 \(0\) 。

代码

#include
#include
#include
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair;
using TP = tuple;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2
//#define rc p*2+1
//#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
//#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 200010;

LL T, A[35];

void solve()
{
	LL res, ans = 0;
	for (int i = 0; i < 30; i++)
	{
		LL a = A[i] - ans, b = A[i] + A[i + 1] - ans;
		cout << "? " << a << ' ' << b << endl;
		cin >> res;
		if (res == A[i + 1])
			ans ^= (1LL << i);
	}
	cout << "! " << ans << endl;
}

int main()
{
	IOS;
	LL num = 1;
	for (int i = 0; i <= 30; i++)
		A[i] = num, num *= 2;
	cin >> T;
	while (T--)
		solve();

	return 0;
}