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

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

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