Почему на соревнованиях по программированию нужны ответы по модулю некоторого большого простого числа?

Многие конкурсные вопросы требуют подсчитать какое-то очень-очень большое число (скажем, количество перестановок последовательности из 150 элементов, содержащей большое количество дубликатов). Многие языки программирования изначально не поддерживают арифметику произвольной точности, поэтому в интересах справедливости для этих конкурсов имеет смысл не запрашивать у вас точное значение. Таким образом, проблема заключается в следующем: как сайт конкурса может узнать, что у вас есть правильный ответ, если вы не можете его точно вычислить?

Одним из изначально привлекательных вариантов было бы просто запросить ответ по модулю некоторой большой степени двойки (скажем, 2³² или 2⁶⁴), чтобы конкуренты, работающие на таких языках, как C или C++ может просто использовать uint32_t или uint64_t для выполнения всех вычислений, допуская нормальное переполнение, а затем отправлять результаты. Однако это не особенно желательно. Предположим, например, что вопрос следующий:

Вычислите 10 000!

Это число ошеломляюще велико и слишком велико, чтобы поместиться в 32-битное или 64-битное целое число без знака. Однако, если вы просто хотите получить ответ по модулю 2³² или 2⁶⁴, вы можете просто использовать эту программу:

#include <stdio.h>
int main() {
    puts("0");
}

Причина этого в том, что 10000! является произведением не менее 5000 четных чисел, поэтому один из его множителей равен 2⁵⁰⁰⁰. Поэтому, если вам просто нужен ответ по модулю 2³² или 2⁶⁴, вам вообще не нужно его вычислять. Вы можете просто сказать, что результат равен 0 mod 2³² или 2⁶⁴.

Проблема здесь в том, что работа по модулю 2³² или 2⁶⁴ затруднительна, если полученный ответ чисто делится на любое из этих чисел. Однако, если мы работаем по модулю большого простого числа, этот трюк не сработает. Например, число 7 897 987 — простое. Если вы попытаетесь вычислить 10 000! мод 7 897 987, то вы не можете просто сказать «ответ равен 0», потому что ни одно из чисел не умножается на 10 000! являются делителями числа 7 897 987. На самом деле вам придется проделать некоторую работу, чтобы выяснить, чему равно это число по модулю этого большого простого числа. В более общем смысле, работа по модулю большого простого числа обычно требует, чтобы вы вычисляли фактический ответ по модулю этого большого простого числа, а не использовали теоретико-числовые приемы, чтобы полностью пропустить всю работу.

Так зачем работать по модулю 1 000 000 007? Это число оказалось простым (поэтому его хорошо использовать в качестве модуля) и меньше, чем 2³¹ - 1, максимальное возможное значение, которое может поместиться в 32-разрядное целое число со знаком. Подпись хороша здесь, потому что в некоторых языках (например, в Java) нет целочисленных типов без знака, а целочисленный тип по умолчанию — это 32-битное целое число со знаком. Это означает, что вы можете работать по модулю 1 000 000 007, не рискуя получить целочисленное переполнение.

Обобщить:

• Работа по модулю большого простого числа делает вероятным, что если ваша программа выдает правильный результат, она на самом деле произвела некоторые вычисления и сделала это правильно.
• Работа по модулю 1 000 000 007 позволяет большому количеству языков использовать встроенные целочисленные типы для хранения и вычисления результата.

Надеюсь это поможет!