Арифметика по модулю: сложение, вычитание, умножение

Арифметика по модулю: почему ответы в задачах берут «по модулю 10⁹+7» и как с этим правильно считать.

Сравнение по модулю: a ≡ b (mod m) означает, что m делит a − b, то есть a и b дают одинаковый остаток при делении на m.

Зачем это в олимпиадах

Огромное число комбинаторных и теоретико-числовых задач имеют гигантские ответы — факториалы, степени, числа сочетаний, которые не помещаются ни в какой целочисленный тип. Поэтому в условии пишут: «выведите ответ по модулю 10⁹+7». Это не каприз: модуль выбран простым, чуть меньше 2ᶜ¹, так что произведение двух остатков помещается в 64-битное число. Чтобы решать такие задачи, нужно уметь складывать, вычитать и умножать «внутри кольца остатков», не теряя корректности. Это базовый навык — без него не возьмёшь ни одну задачу на подсчёт.

Интуиция: арифметика часов

Модулярная арифметика — это «арифметика циферблата». На часах после 12 идёт снова 1: 11 + 3 = 14 ≡ 2 (mod 12). Мы работаем не с самими числами, а с их остатками. Чудо в том, что остаток совместим со сложением и умножением: если заменить любые слагаемые или множители на их остатки, итоговый остаток не изменится. Формально, если a ≡ a' и b ≡ b' (mod m), то:

a + b ≡ a' + b', a − b ≡ a' − b', a · b ≡ a' · b' (mod m)

Это позволяет брать модуль на каждом шаге, удерживая числа маленькими, и получать тот же остаток, как если бы мы считали «по-честному» огромное число, а потом взяли остаток.

Сложение, вычитание, умножение по модулю

Сложение и умножение прямолинейны: считаем и берём % m. Тонкость — вычитание: разность может стать отрицательной, а нам обычно нужен остаток в диапазоне [0, m). В Python оператор % уже возвращает неотрицательный результат при положительном m, поэтому (a - b) % m «само» приводит к правильному виду. В C++ пришлось бы писать ((a - b) % m + m) % m — запомните этот паттерн для переноса решений.

MOD = 10**9 + 7
a, b = 7_000_000_000, 4_500_000_000

print((a + b) % MOD)        # сложение
print((a - b) % MOD)        # вычитание, результат неотрицателен
print((b - a) % MOD)        # даже когда b < a — Python вернёт остаток в [0, MOD)
print((a % MOD) * (b % MOD) % MOD)  # умножение: сперва уменьшаем множители

Вывод:

Обратите внимание на (b - a) % MOD: b − a отрицательно, но Python вернул 500000021 ≡ b − a (mod MOD). И на умножение: мы взяли % MOD у каждого множителя до перемножения. В Python это не обязательно (переполнения нет), но в C++ без этого a * b вылетит за long long. Привыкайте уменьшать на каждом шаге — это правильная привычка.

Накопление произведения: факториал по модулю

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

MOD = 10**9 + 7

def factorial_mod(n, mod):
    res = 1
    for i in range(2, n + 1):
        res = res * i % mod      # модуль на каждом шаге
    return res

print(factorial_mod(10, MOD))     # 10! = 3628800, помещается
print(factorial_mod(100, MOD))    # 100! огромно, но остаток мал
print(factorial_mod(1000, MOD))

Вывод:

3628800
437918130
641419708

Здесь видна суперсила Python для теории чисел: даже если убрать % mod, 1000! вычислится точно (целые длинные), просто медленнее. Но мы всё равно берём модуль, потому что (а) ответ нужен именно по модулю и (б) при переносе на C++ без модуля будет переполнение. Длинная арифметика Python — отличная страховка: можно сравнить «честный» результат с модульным и поймать ошибку.

Что нельзя делать наивно

Сложение, вычитание, умножение переносятся в кольцо остатков без проблем. А вот деление так не работает: (a / b) % m в общем случае бессмысленно, ведь a / b может быть нецелым. Деление по модулю требует понятия обратного элемента — числа b⁻¹, для которого b · b⁻¹ ≡ 1 (mod m). Этому посвящены следующие два урока. Пока запомните: умножать можно смело, делить — только через обратный.

MOD = 7
# Наивное "деление" ломается:
print((6 // 2) % MOD)              # 3 — случайно совпало
# но (6 % MOD) // (2 % MOD) вообще не определено как операция в кольце
# Правильно: умножить на обратный к 2 (он равен 4, т.к. 2*4=8≡1 mod 7)
inv2 = 4
print(6 * inv2 % MOD)              # 24 % 7 = 3 — корректно

Вывод:

3
3

Разбор задачи: последняя цифра и сумма большого ряда

Модулярная арифметика отвечает на «хвостовые» вопросы без вычисления огромных чисел. «Какая последняя цифра у 2¹⁰⁰?» — это 2¹⁰⁰ mod 10. «Чему равна сумма 1²+2²+…+n² по модулю 10⁹+7 для n = 10¹²?» — берём формулу n(n+1)(2n+1)/6 и считаем по модулю, заменяя деление на 6 умножением на обратный (тема следующих уроков). Покажем оба приёма.

MOD = 10**9 + 7

# Последняя цифра 2^100 — это остаток по модулю 10
print(pow(2, 100, 10))

# Сумма квадратов до n по модулю: n(n+1)(2n+1)/6
def sum_squares_mod(n, mod):
    inv6 = pow(6, mod - 2, mod)            # обратный к 6 по модулю
    return (n % mod) * ((n + 1) % mod) % mod * ((2 * n + 1) % mod) % mod * inv6 % mod

n = 10**12
print(sum_squares_mod(n, MOD))
# сверка на маленьком n с прямой суммой
print(sum_squares_mod(10, MOD), sum(i * i for i in range(1, 11)))

Вывод:

6
691166305
385 385

Последняя цифра 2¹⁰⁰ равна 6 — найдена одним взятием остатка по модулю 10, без вычисления самого 2¹⁰⁰. А сумма квадратов для n = 10¹² посчитана по модулю мгновенно и на маленьком n = 10 совпала с прямым суммированием (385). Так модуль превращает «невычислимые» величины в короткие остатки.

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

Отрицательные остатки. В Python % безопасен; в C++/Java для вычитания нужен паттерн ((x % m) + m) % m.
Не делите. (a / b) % m неверно; используйте обратный элемент.
Берите модуль рано и часто. Иначе при переносе на язык с фиксированным int — переполнение.
Модуль может быть не простым. Тогда обратный существует не для всех чисел (нужна взаимная простота). Об этом — дальше.

Итог

Сравнение a ≡ b (mod m) — равенство остатков; m | (a − b).
Сложение, вычитание и умножение совместимы с взятием остатка — берите % m на каждом шаге.
В Python % всегда неотрицателен при m > 0; в C++ помните про + m для вычитания.
Деление по модулю напрямую невозможно — нужен обратный элемент (следующие уроки).