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.

Рассмотрим такую задачу: даны три целых числа $$$x$$$, $$$y$$$ и $$$m$$$, $$$0 \leqslant x,y < m < 2^{32}$$$, найти $$$xy\bmod m$$$. По-хорошему хотелось бы просто перемножить эти два числа, а потом применить операцию остатка:

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

Как вы, возможно, догадываетесь, это решение неверное. Всё дело в том, что в такой процедуре возможно переполнение: операция x * y выполняется в типе uint32_t, и на самом деле промежуточным результатом выполнения этой операции будет не $$$xy$$$, а $$$xy\bmod2^{32}$$$. Если после этого взять результат по модулю $$$m$$$, он может отличаться от правильного:

Выход прост — перемножать необходимо в большем типе:

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

Если так делать, то, поскольку $$$xy<2^{64}$$$, это произведение точно не переполнится, и после взятия результата по модулю получится правильный ответ.

Вопрос: а что делать, если $$$x$$$, $$$y$$$ и $$$m$$$ могут быть больше?

Сейчас проходит церемония закрытия IMO 2021.

Лучшими странами оказались:

1. Китайская Народная Республика, 208 очков
2. Россия, 183 очка
3. Республика Корея, 172 очка
4. Соединённые Штаты Америки, 165 очков
5. Канада, 151 очко

Ссылка на английскую трансляцию: https://youtube.com/watch?v=LHi_xjvLEbI

На русскую: 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