Модульная арифметика: зачем везде 10^9+7 и как с ней работать

Коротко

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

В алгоритмических задачах ответ часто оказывается астрономически большим — число сочетаний, количество путей, значение рекуррентности. Хранить такое число целиком неудобно: в C++ оно переполнит long long, в Python займёт мегабайты и будет считаться медленно.

Поэтому условие просит: «выведите ответ по модулю 10⁹+7». Мы работаем с остатками, и все промежуточные значения остаются маленькими.

Основное свойство

Остаток «переживает» сложение, вычитание и умножение:

(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 mod m) · (b mod m)) mod m

Практический смысл: можно брать остаток на каждом шаге, а не только в конце. Результат не изменится, а числа останутся ограниченными.

MOD = 10 ** 9 + 7

# считаем факториал 100000 по модулю — числа не растут
factorial = 1
for i in range(1, 100001):
    factorial = factorial * i % MOD

print(factorial)   # 457992974

Без взятия остатка это число имело бы больше 450 тысяч цифр.

Почему именно 10⁹+7

Три причины, и все практические.

Это простое число. Простота нужна для деления — по малой теореме Ферма обратный элемент существует для любого числа, не кратного модулю. С составным модулем деление работает не всегда.

Оно чуть меньше 2³⁰. Значит любое число по этому модулю помещается в 32-битный тип. Удобно и экономно.

Произведение двух таких чисел помещается в 64 бита. Максимум (10⁹+6)² ≈ 10¹⁸, а long long вмещает до 9.2·10¹⁸. То есть умножение не переполнится — это ключевое свойство для C++ и Java.

Другие популярные модули: 10⁹+9 (тоже простое, используют для второго хеша), 998244353 (удобен для быстрого преобразования Фурье), 2⁶¹−1 (простое Мерсенна для хеширования).

Вычитание: главная ловушка

В математике остаток всегда неотрицателен. В большинстве языков программирования — нет.

# Python ведёт себя математически корректно
print((-7) % 5)    # 3

// Java, C++, C#, JavaScript, Go — остаток сохраняет знак делимого
(-7) % 5   // -2

Поэтому в этих языках после вычитания нужна поправка:

int diff = ((a - b) % MOD + MOD) % MOD;

Разбор: (a - b) % MOD может дать значение от -(MOD-1) до MOD-1. Прибавление MOD делает его положительным, а повторный остаток возвращает в нужный диапазон.

Python от этой проблемы избавлен, но знать её нужно — при переносе решения на другой язык это самый частый источник расхождений.

Деление через обратный элемент

Разделить по модулю напрямую нельзя: (a / b) mod m не равно (a mod m) / (b mod m).

Вместо деления умножают на обратный элемент — число b⁻¹, для которого b · b⁻¹ ≡ 1 (mod m).

Для простого модуля его даёт малая теорема Ферма:

b^(m-1) ≡ 1 (mod m)   ⟹   b^(m-2) ≡ b^(-1) (mod m)

MOD = 10 ** 9 + 7


def inverse(x: int) -> int:
    return pow(x, MOD - 2, MOD)


def divide(a: int, b: int) -> int:
    return a * inverse(b) % MOD


print(divide(10, 3))          # 333333338
print(333333338 * 3 % MOD)    # 10 — проверка сошлась

Стоимость обратного элемента — O(log m) за счёт быстрого возведения в степень.

Для составного модуля теорема Ферма неприменима — там нужен расширенный алгоритм Евклида, и обратный элемент существует только если числа взаимно просты.

Практика: сочетания по модулю

Классическая задача — посчитать C(n, k) для больших n. Формула содержит деление, поэтому без обратных элементов не обойтись.

MOD = 10 ** 9 + 7
MAX = 10 ** 6

# предподсчёт факториалов
fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD

# обратные факториалы: считаем последний, остальные назад
inv_fact = [1] * (MAX + 1)
inv_fact[MAX] = pow(fact[MAX], MOD - 2, MOD)
for i in range(MAX, 0, -1):
    inv_fact[i - 1] = inv_fact[i] * i % MOD


def combinations(n: int, k: int) -> int:
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD


print(combinations(10, 3))        # 120
print(combinations(1000000, 500000))   # мгновенно

Приём с пересчётом обратных факториалов «назад» стоит запомнить: он даёт все обратные элементы за один вызов pow вместо n вызовов. Основан на тождестве inv_fact[i-1] = inv_fact[i] · i.

Быстрое возведение по модулю

Основной инструмент модульной арифметики. В Python встроен:

pow(base, exponent, modulus)

Реализация вручную для понимания:

def power_mod(base: int, exp: int, mod: int) -> int:
    result = 1
    base %= mod

    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1

    return result

Китайская теорема об остатках

Иногда результат нужен по составному модулю или требуется восстановить число по нескольким остаткам. Если модули попарно взаимно просты, система

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)

имеет единственное решение по модулю m₁·m₂. Это позволяет считать по нескольким маленьким простым модулям и собирать ответ — приём используется в криптографии и при работе с большими числами.

Что нельзя делать по модулю

Сравнивать на больше-меньше. После взятия остатка порядок теряется: число 1 может быть остатком и от 1, и от 10⁹+8.

Делить нацело. (a // b) % m не имеет смысла в модульной арифметике.

Извлекать корень напрямую. Квадратный корень по модулю — отдельная непростая задача (алгоритм Тонелли-Шенкса).

Возводить в степень по модулю в показателе. a^(b mod m) не равно a^b mod m. Показатель уменьшается по модулю m-1 (по теореме Ферма), а не по m.

Частые ошибки

Взятие остатка только в конце. Промежуточные значения переполнятся (в C++/Java) или замедлят программу (в Python).

Отрицательный остаток после вычитания. В языках кроме Python — гарантированный баг.

Деление вместо умножения на обратный элемент. Даёт неверный ответ, причём иногда близкий к правильному, что затрудняет отладку.

Обратный элемент от нуля. Не существует. Проверяйте, что делитель не кратен модулю.

Составной модуль с теоремой Ферма. Формула pow(b, m-2, m) верна только для простого m.

Что запомнить

• Остаток можно брать на каждом шаге при сложении, вычитании и умножении.
• 10⁹+7 выбран потому, что простое, помещается в 32 бита, а квадрат — в 64.
• В языках кроме Python после вычитания добавляйте + MOD перед повторным остатком.
• Деление — это умножение на обратный элемент pow(b, m-2, m), работает только для простого модуля.
• Обратные факториалы считаются за один pow пересчётом в обратном порядке.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→