Podzadatak 1

Primetimo da je jedan od brojeva ~X,Y~ manji ili jednak ~\sqrt{A}~, pa je dovoljno izvršiti pretragu po svim brojevima ~X~ do ~\sqrt{A}~, gde proveravamo da je ~Y = \frac{A}{X}~ ceo broj i da je ~X \text{ XOR } Y = B~. Vremenska složenost po primeru je ~O(\sqrt{A})~.

Podzadatak 2

Da bi se smanjio broj kandidata za broj ~X~ primetimo da ~X~ mora biti delilac broja ~A~. Može se iskoristiti bilo koji brzi algoritam za faktorizaciju celih brojeva. Jedan takav algoritam je Pollard-Rho algoritam, koji se najčešće implementira zajedno sa Miller-Rabin algoritmom za proveru da li je broj prost. Ovaj algoritam ima vremensku složenost ~O(\sqrt[4]{n})~ za nalaženje jednog faktora broja ~n~, ali ima veliku skrivenu konstantu i iz tog razloga nije dovoljno brz.

Glavno rešenje

Najpre, primetimo da pri računanju XOR vrednosti i proizvoda dva broja, najnižih ~n~ bitova rezultata zavise samo od najnižih ~n~ bitova operanada. Ako posmatramo fiksne vrednosti ~n, a, b~, gde je ~0 \leq a, b < 2^n~ i ~a~ je neparno, pokazuje se da postoji najviše ~2^{\lfloor\frac{n+3}{2}\rfloor}~ rešenja jednačine

~xy \equiv a \mod 2^n, x \text{ XOR } y = b~,

gde su ~x,y~ nepoznate, takođe brojevi iz skupa ~[0, 2^n)~. Iz tog razloga, ako fiksiramo najnižih ~n~ bitova broja ~X~, ovakvih validnih parcijalnih rešenja neće biti više od ~2^{\lfloor\frac{n+3}{2}\rfloor}~. Ova parcijalna rešenja možemo generisati rekurzivno. U ~n~ tom nivou rekurzije imamo ne više od ~2^{\lfloor\frac{n+3}{2}\rfloor}~ poziva. Dovoljno je pronaći samo prvih ~31~ bitova broja ~X~, jer je zbog uslova ~XY=A~ bar jedan od brojeva ~X,Y~ manji ili jednak ~A~, a uvek možemo da pretpostavimo da je to broj ~X~. Sumiranjem po ~n~ dobijamo da ima ~O(\sqrt[4]{A})~ rekurzivnih poziva, pa je upravo ovo vremenska složenost rešavanja jednog test primera.