Nice problem, I did not prove my solution tbh I just dry ran in binary and figured its true for all 2^n — 1. Could you provide a formal proof or hint

Umm, why powers of 2 fail

suppose i take ai = 32

then shouldn't gcd be equal for all k??

And another thing. to check wether a number is 2 ^ n - 1

just use

if (x & (x + 1)) == 0)

gcd(a[i], k) is equal to gcd(a[i]+k, k), so gcd(a[i], k) = gcd(a[i]⊕k, k) when a[i]&k==0. Since k>=10^49, a[i]&k==0 can be true for any a[i]. So the answer is n always? But why it is not correct?

UPD: Sorry, I understood. The statement tells us that it must be true for ALL k, not ANY

Can someone explain why the answer is true for all 2^n — 1 and not 2^n and 0

For a_i = 3, k = 2^200 + 2 doesn't work because gcd(a_i, k) = 3, gcd(a_i, k xor a_i) = 1

For a_i = 2^n for arbitrary n, gcd(a_i, k xor a_i) is just gcd(a_i, k + a_i) or gcd(a_i, k — a_i), both are equal to gcd(a_i, k)

Is it possible to recommend problems to contest-setters? I have one in mind based on a number theory thing I found myself

your solution for $$$2^n-1$$$ does not work.

and $$$2^n$$$ works but i dont know other ones work too or not.

$$$2^n$$$ has only one bit in binary

so it would either be $$$gcd(a, k) == gcd(a, k- a)$$$

or $$$gcd(a, k) == gcd(a, k + a)$$$

two statements are always true tho for $$$10^{49}\le k$$$

now why $$$2^n-1$$$ does not work:

take $$$n=2, 2^2-1 = 3$$$

you can always find such $$$r:$$$

$$$10^{49} \le 2^r+1 \le 10^{100}, gcd(2^r+1,3) = 3$$$

if you do $$$(2^r+1) \oplus 3$$$ then you can represent it like this

$$$(2^r + 1) - 1 + 2 = 2^r + 2$$$

so $$$gcd(3,2^r+1) \ne gcd(3,2^r+2)$$$