Link to the problem - F - Coincidence
@ssjgz as again can you help?
Sorry - I have limited time today and can’t immediately figure this one out
Some suggestions, though:
Experiment - pick an x, and, starting with y == x, increment the values of y and calculate y \mod x and y \oplus x. Can we keep increasing y for ever and still finding y's such that y \mod x = y \oplus x? If not, what is the maximum value of y for your given x? Why? How does it relate to the binary representation of x?
For x=128, for example, we get “a lot” of values of y - why is this? For x=132, we get “fewer” values of y - what is the pattern with the “missing” y, and how does it relate to the binary representation of x?
Is there a way, just from looking at the binary representation of x, of immediately counting all y such that y \mod x = y \oplus x? Can we, knowing about the patterns of binary representations of successive integers, count all y for a range of x at a time without having to consider each x individually?
I have a suspicion that the key to the solution is in the above questions, but don’t know for sure - I definitely think they’re worth exploring, though
a quick explanation by someone at codeforces : link
I saw that already but to be honest did not understand it. Hoping that someone can provide a more detailed explanation.
English explanations at the end of the pdf.