Hi there!

Recently after Codeforces Global Round 21 Um_nik noticed that he might be the ninth or tenth person to reach 3600 rating points, but still he did it earlier than Petr. I wondered whether Um_nik really was that attentive to know for sure how many people reached 3600 before him. As this is an objective truth or an objective misconception, I decided to simply check it.

Consider the following problem: given three integers $$$x$$$, $$$y$$$ и $$$m$$$, $$$0 \leqslant x,y < m < 2^{32}$$$, calculate $$$xy\bmod m$$$. The easy way is just to multiply these numbers and apply the modulo operation:

uint32_t prod(const uint32_t x, const uint32_t y, const uint32_t m)
{
	return x * y % m;
}

As you might have guessed, this solution is wrong. The thing is that an overflow is possible in such a procedure: the operation x * y is performed in the typeuint32_t, and in fact the intermediate result of this operation will not be $$$xy$$$, but $$$xy\bmod2^{32}$$$. If after that we take the result modulo $$$m$$$, it may differ from the correct one:

The way out is simple — you need to multiply in a larger type:

uint64_t prod_uint64(const uint64_t x, const uint64_t y, const uint64_t m)
{
	return x * y % m;
}

If you do this, then, since $$$xy<2^{64}$$$, this product will definitely not overflow, and after taking the result modulo, you will get the correct answer.

The question is: what if $$$x$$$, $$$y$$$ and $$$m$$$ can be greater than $$$2^{32}$$$?

IMO 2021 closing ceremony is taking place now.

Top countries were:

1. People's Republic of China, 208 points
2. Russian Federation, 183 points
3. Republic of Korea, 172 points
4. United States of America, 165 points
5. Canada, 151 points

English: https://youtube.com/watch?v=LHi_xjvLEbI

Russian: https://youtube.com/watch?v=23cTkofxbq4

IMO 2021

IMO 2021 opening ceremony takes place right now. Join the chat!

Russian: https://www.youtube.com/watch?v=c3APd3bCrFI

English: https://www.youtube.com/watch?v=DpZnQuUI27Y