GCD Guess

Created by LXC on Sun Sep 24 22:14:18 2023

https://codeforces.com/problemset/problem/1665/D

ranting: 2000

tag: bitmasks, chinese remainder theorem, constructive algorithms, games, interactive, math, number theory

problem

交互题

在不超过30次操作内求出$x$。 $1 \le x \le 10^9$

每次操作可以选定任意两个不同的数$a$和$b$，查询得到$gcd(a+x, b+x)$

solution

假设$x \bmod 2^k = r$，我们求$gcd (x + 2^k - r, 2^{k+1})$，利用gcd的性质，在操作查询时可以写为$gcd (x + 2^k - r, 2^{k+1} + x + 2^k - r)$

由于$x+2^k-r$是$2^k$的倍数，不妨设$x+2^k-r = t\times 2^k, t\ge 1$，而$x = (t-1)\times 2^k+r$

我们的查询实际上是求$gcd(t\times2^k, 2\times2^k)$。当$t$是偶数时$gcd=2^{k+1}$，因此$x \bmod 2^{k+1} = 2^k+r$；当$t$是奇数时$gcd=2^k$，因此$x \bmod 2^{k+1} = r$。

已知$x \bmod 2^0=0$

由于$x \le 10^9 < 2^{30}$，所以在30次操作时可以得到$x \bmod 2^{30} = x$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


ll h = 1231321;

ll ask(ll a, ll b) {
    cout << "? " << a << " " << b << endl;
    int rt;
    cin >> rt;
    // rt = gcd(h+a, h+b);
    return rt;
}

void sol() {
    ll r = 0;
    for (int i=0; i<30; i++) {
        ll rt = ask((1LL<<i)-r, (3LL<<i)-r);
        if (rt == (1<<i+1)) r |= 1LL<<i;
    }
    cout << "! " << r << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}