interactive-gcd-xor (Həll təhlili)

We will iterate over all primes p<5000. Lets say p^k is the biggest power of $p$ that divides $a$ and p^l is the biggest power of $p$ that divides $b$. Then the \mathrm{lcm}(a,b)=\Pi_{p<5000 \text{prime}}p^{\max(k,l)}.

If we now query some p^n, such that p^n\ge\max(p^l,p^k), the interactor returns \text{QUERY}(p^n)=\gcd(p^n,a) \oplus \gcd(p^n,b)=\gcd(p^n,p^k) \oplus \gcd(p^n,p^l)=(p^k)\oplus(p^l).

This is actually sufficient to solve subtasks $1$ and $2$:

In subtask $1$, we know, that b=1, so p^l=1. Therefore we can just derive p^k=\text{QUERY}(p^n) \oplus 1.

In subtask $2$, since a \neq b, x \neq y, p^k \neq p^l. WLOG, let p^k>p^l. Then p^k\ge p\cdot p^l\ge2 \cdot p^l, so the highest bit set in p^k will not be xored by p^l. At the same time, since p\ge 2, the highest bit of p^k is only set for one unique $k$, so we can derive $k$ from that (Note that we can pretty easily find p^l=\text{QUERY}(p^n) \oplus p^k.

The only case left is for p^k=p^l, in which case \text{QUERY}(p^n)=0. Since a \neq b. If that happens, we want to save $p$ for later. Since a\neq b, there exists at least one prime $q$, such that q^{k1} \neq q^{l1}, WLOG q^{k1} > q^{l1}. Lets save this q,k1,l1. Later we can then iterate over all previously unsolved primes $p$ and ask \text{QUERY}(q^{k1} \cdot p^n)=(q^{k1} \cdot p^k) \oplus (q^{l1} \cdot p^k). Since q^{k1} \cdot p^n \ge 2 \cdot q^{l1} \cdot p^k, the highest bit of q^{k1} \cdot p^n stays set, and since p\ge 2, it uniquely determines $k$.

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll PMAX=5000;
ll AMAX=1e9;

ll query(ll c){
    cout<<"? "<<c<<'\n';
    fflush(stdout);
    ll a;
    cin>>a;
    return a;
}

int main() {
    vector<pair<ll,ll>> later;
    ll val=1, c1=-1, c2=-1;

    for (ll i=2;i<=PMAX;i++){
        bool p=1;
        for (ll j=2;j*j<=i;j++) if ((i%j)==0) p=0;
        if (!p) continue;
        ll q=i;
        vector<ll> pot(60,0);
        while (q*i<AMAX){
            pot[__builtin_clz(q)]=q;
            q*=i;
        }
        pot[__builtin_clz(q)]=q;
        ll ret;
        ret=query(q);

        ll r1,r2;
        if (ret==0) later.push_back({q,i});
        else{
            r1=pot[__builtin_clz(ret)];
            r2=ret^r1;
            val*=r1;
            c1=r1;
            c2=r2;
        }
    }
    for (auto p:later){
        ll q=p.first, i=p.second;
        ll snd=c1;
        while (snd*i<AMAX) snd*=i;
        ll ret=query(snd);
        ll ans=1;
        while (((c1*ans)^(c2*ans))!=ret){
            ans*=i;
        }
        val*=ans;

    }
    cout<<"! "<<val<<'\n';
    fflush(stdout);

    return 0;
}