How to solve F - Coincidence from AtCoder Beginner Contest 138?

Link to the problem - F - Coincidence

@ssjgz as again can you help?:smiley:

Sorry - I have limited time today and can’t immediately figure this one out :confused:

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 :slight_smile:

1 Like

a quick explanation by someone at codeforces : link

1 Like

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.

1 Like