Hello CODEFORCES...
I hope this blog finds you well! Well, this is my second original problem, find the first one HERE! Please give me valuable feedback and tell me what should be the rating of this problem according to you.
Problem link: https://mirror.codeforces.com/contestInvitation/e767d64e11d327a042c31e01ec9b5cff93950215
I would be more than happy if you will take interest in solving the problem and make (m)a(ny) submission(s)!
Edit 1: Sorry, PS had a major mistake, link is updated.
Edit 2: Problem has a major flaw, and needs to be changed drastically, sorry for the inconvenience caused.
Edit 3: Problem and the model solution is fully ready, give it another shot! ( Special thanks to feev1x for providing the correct logic! See -> https://mirror.codeforces.com/blog/entry/144422?#comment-1291770 )









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, not so formal, but XOR is addition and subtraction without carry, and gcd(a,b)=gcd(a,a+b) and gcd(a,b)=gcd(a,|a-b|). Thank you for making a submission though!
I understand that, but how do you prove that the statement is false for rest of the numbers?
$$$2^n-1$$$ does not even work. Take $$$\gcd(7,14) \neq \gcd(7,7\^14 = 9)$$$ for example. only $$$2^n$$$ or $$$0$$$ work.
read constraints on k
Those do not matter, you can have k or k + 2^50*a[i]. Both have same result. Fix your problem please.
.
$$$\gcd(7,14 + 7*2^{50}) = 7$$$. However $$$7 \oplus (14 + 7*2^{50}) = 9 + 7*2^{50}$$$, and $$$\gcd(7, 9 + 7*2^{50}) = \gcd(7,9)=1$$$.
Umm, why powers of 2 fail
suppose i take ai = 32
then shouldn't gcd be equal for all k??
Of course not, with an even number the GCD will be even with odd it'll be odd
And another thing. to check wether a number is
2 ^ n - 1just use
Yes, I know, I used that code to generate numbers such as 2^n-1. And it finally made it to the solution as well...
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)$$$
Till now I have found
and 0 working
Oh I see, that is clever. Thank you for notifying this to me, you really saved my hard work put in to prepare this problem!