Модулярная арифметика

Почему в задачах просят ответ «по модулю 10^9+7» и как правильно считать в этой арифметике, включая деление через обратный элемент.

Модулярная арифметика — вычисления, в которых все числа берутся по модулю m (остаток от деления на m); это позволяет работать с гигантскими ответами, не теряя точности.

Зачем это нужно

Во многих комбинаторных задачах ответ — астрономическое число (число способов, перестановок), которое не помещается в стандартные типы и слишком велико для вывода. Поэтому условие просит вывести ответ по модулю большого простого, обычно 10^9 + 7 или 998244353. Это не усложнение ради усложнения: модулярная арифметика позволяет считать промежуточные результаты в управляемых пределах. Но у неё свои правила — особенно для деления, которое работает не так, как привыкли. Освоить эти правила обязательно для всего комбинаторного блока.

Что сохраняется, а что нет

Хорошая новость: сложение, вычитание и умножение «дружат» с модулем — можно брать остаток на любом шаге:

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a · b) mod m = ((a mod m) · (b mod m)) mod m
Вычитание: (a − b) mod m = (a − b + m) mod m — прибавляем m, чтобы избежать отрицательного остатка.

Плохая новость: деление так не работает. (a / b) mod m ≠ (a mod m) / (b mod m) в общем случае. Деление требует особого приёма — обратного элемента.

MOD = 1_000_000_007

a, b = 123456789012345, 987654321098765
print("Сумма по модулю:    ", (a + b) % MOD)
print("Произведение по мод:", (a % MOD) * (b % MOD) % MOD)
# Вычитание с защитой от отрицательного результата:
print("Разность по модулю: ", (a - b + MOD) % MOD)

Обрати внимание на вычитание: (a - b + MOD) % MOD. Прибавление MOD гарантирует неотрицательный результат, даже если a < b. В Python оператор % и так возвращает неотрицательный остаток, но привычка добавлять MOD страхует и переносима на другие языки.

Вывод:

Сумма по модулю:     102333333
Произведение по мод: 100638300
Разность по модулю:  473962966

Деление: обратный элемент по модулю

«Разделить на b по модулю m» означает умножить на обратный элемент b⁻¹ — такое число, что b · b⁻¹ ≡ 1 (mod m). Когда модуль m — простое число (а 10^9+7 простое!), обратный элемент даёт малая теорема Ферма: b⁻¹ ≡ b^(m−2) (mod m). А возводить в степень мы уже умеем за O(log m) из прошлого урока!

MOD = 1_000_000_007

def power(b, e, m):                     # быстрое возведение в степень
    r = 1; b %= m
    while e:
        if e & 1: r = r * b % m
        b = b * b % m
        e >>= 1
    return r

def inv(a):
    return power(a, MOD - 2, MOD)        # обратный по малой т. Ферма

# Хотим посчитать (10 / 3) mod p
a, b = 10, 3
res = a % MOD * inv(b) % MOD
print("10 * inv(3) mod p =", res)
# Проверка: (3 * res) mod p должно дать 10
print("Проверка 3*res:", 3 * res % MOD)

Логика: вместо деления на 3 мы умножаем на inv(3) = 3^(p−2) mod p. Проверка подтверждает корректность: 3 · (10·3⁻¹) ≡ 10 (mod p). Именно так в комбинаторике вычисляют, например, C(n, k) = n! / (k!·(n−k)!) по модулю — деление на факториалы заменяют умножением на их обратные элементы.

Вывод:

10 * inv(3) mod p = 333333339
Проверка 3*res: 10

Почему именно 10^9+7

Свойство	Зачем
Простое число	работает малая теорема Ферма для обратного элемента
Близко к 10^9	результат умножения двух остатков (<10^18) помещается в 64-битный тип
Стандарт	привычно и легко не ошибиться

В Python переполнения нет (целые неограничены), но в C++/Java выбор модуля около 10^9 критичен: произведение двух чисел до 10^9 укладывается в 10^18 < предела 64-битного типа.

Подводные камни

Деление ≠ обычное деление. Только через обратный элемент; иначе ответ неверен.
Обратный по Ферма — только для простого модуля. Для составного m нужен расширенный алгоритм Евклида (и обратный существует лишь при взаимной простоте).
Обратного к нулю не существует. Деление на 0 по модулю не определено.
Бери модуль почаще. В языках с фиксированными целыми не дай произведению выйти за пределы типа — % MOD после каждого умножения.

Итог

Сложение, вычитание и умножение совместимы с модулем; при вычитании добавляй + m для неотрицательного результата.
Деление по модулю — это умножение на обратный элемент b⁻¹.
Для простого модуля b⁻¹ ≡ b^(m−2) по малой теореме Ферма, считается быстрым возведением в степень.
10^9+7 выбран как простое, удобное для 64-битной арифметики; обратного к 0 не бывает.