interactive-gcd-xor#12469

interactive-gcd-xor (Розбір)

Ми будемо перебирати всі прості числа $p < 5000$ p<5000. Нехай $p^{k}$ p^k — найбільший степінь $p$ , що ділить $a$ , а $p^{l}$ p^l — найбільший степінь $p$ , що ділить $b$ . Тоді $lcm (a, b) = Π_{p < 5000 просте} p^{m a x (k, l)}$ \mathrm{lcm}(a,b)=\Pi_{p<5000 \text{ просте}}p^{\max(k,l)}.

Якщо тепер зробити запит для деякого $p^{n}$ p^n, такого що $p^{n} \geq max (p^{l}, p^{k})$ p^n\ge\max(p^l,p^k), інтерактор повертає $QUERY (p^{n}) = g cd (p^{n}, a) \oplus g cd (p^{n}, b) = g cd (p^{n}, p^{k}) \oplus g cd (p^{n}, p^{l}) = (p^{k}) \oplus (p^{l})$ \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).

Цього достатньо для розв'язання підзадач $1$ і $2$ :

У підзадачі $1$ відомо, що $b = 1$ b=1, тому $p^{l} = 1$ p^l=1. Отже, можна просто знайти $p^{k} = QUERY (p^{n}) \oplus 1$ p^k=\text{QUERY}(p^n) \oplus 1.

У підзадачі $2$ , оскільки $a \neq = b$ a \neq b, $x \neq = y$ x \neq y, маємо $p^{k} \neq = p^{l}$ p^k \neq p^l. Без втрати загальності нехай $p^{k} > p^{l}$ p^k>p^l. Тоді $p^{k} \geq p \cdot p^{l} \geq 2 \cdot p^{l}$ p^k\ge p\cdot p^l\ge2 \cdot p^l, тому старший встановлений біт у $p^{k}$ p^k не буде змінений XOR-ом з $p^{l}$ p^l. Водночас, оскільки $p \geq 2$ p\ge 2, старший біт $p^{k}$ p^k встановлений лише для одного унікального $k$ , тому можна знайти $k$ з цього (зауважимо, що $p^{l} = QUERY (p^{n}) \oplus p^{k}$ p^l=\text{QUERY}(p^n) \oplus p^k знаходиться досить легко).

Єдиний випадок, що залишився, — це $p^{k} = p^{l}$ p^k=p^l, при якому $QUERY (p^{n}) = 0$ \text{QUERY}(p^n)=0. Оскільки $a \neq = b$ a \neq b, якщо таке трапляється, ми хочемо зберегти $p$ на потім. Оскільки $a \neq = b$ a\neq b, існує хоча б одне просте $q$ , таке що $q^{k 1} \neq = q^{l 1}$ q^{k1} \neq q^{l1}, без втрати загальності $q^{k 1} > q^{l 1}$ q^{k1} > q^{l1}. Збережемо це $q, k 1, l 1$ q,k1,l1. Пізніше можна перебрати всі раніше нерозв'язані прості $p$ і зробити запит $QUERY (q^{k 1} \cdot p^{n}) = (q^{k 1} \cdot p^{k}) \oplus (q^{l 1} \cdot p^{k})$ \text{QUERY}(q^{k1} \cdot p^n)=(q^{k1} \cdot p^k) \oplus (q^{l1} \cdot p^k). Оскільки $q^{k 1} \cdot p^{n} \geq 2 \cdot q^{l 1} \cdot p^{k}$ q^{k1} \cdot p^n \ge 2 \cdot q^{l1} \cdot p^k, старший біт $q^{k 1} \cdot p^{n}$ q^{k1} \cdot p^n залишається встановленим, і оскільки $p \geq 2$ p\ge 2, він однозначно визначає $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;
}

C++