kz-maxx

RU KZ
← Главная

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

Остатки, mod, сложение, умножение, степень, обратный элемент и деление по модулю

Что такое модуль?

Модуль — это остаток от деления.

Например: 

17 mod 5 = 2

Потому что: 

17 = 5 * 3 + 2

В C++ остаток берется через оператор: 

%

Пример в C++

int a = 17;
int m = 5;

cout << a % m;

Output: 

2
В олимпиадных задачах часто просят вывести ответ по модулю, например по модулю 1e9 + 7.

Зачем нужен mod?

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

ответ может быть 10^100
но мы выводим answer % MOD

Самый популярный модуль: 

const long long MOD = 1000000007;

Сравнение по модулю

Два числа равны по модулю m, если они дают одинаковый остаток при делении на m. 

17 mod 5 = 2
7 mod 5 = 2

Поэтому: 

17 ≡ 7 (mod 5)

Это читается так: 17 сравнимо с 7 по модулю 5.

Сложение по модулю

Если нужно сложить два числа и взять mod: 

(a + b) % MOD

Пример: 

a = 8
b = 9
MOD = 10

(8 + 9) % 10 = 17 % 10 = 7

Вычитание по модулю

При вычитании может получиться отрицательное число.

Например: 

3 - 7 = -4

Поэтому безопасная формула: 

(a - b + MOD) % MOD

Если числа могут быть сильно большими, можно писать: 

((a - b) % MOD + MOD) % MOD

Умножение по модулю

Для умножения: 

(a * b) % MOD

Но если a и b большие, может быть overflow. Поэтому обычно используем long long. 

long long res = a * b % MOD;

Базовые функции

const long long MOD = 1000000007;

long long add(long long a, long long b) {
    return (a + b) % MOD;
}

long long sub(long long a, long long b) {
    return (a - b + MOD) % MOD;
}

long long mul(long long a, long long b) {
    return a * b % MOD;
}

Нормализация числа

Иногда число может быть отрицательным. Тогда его надо привести к нормальному остатку от 0 до MOD - 1. 

long long norm(long long x) {
    x %= MOD;

    if (x < 0) {
        x += MOD;
    }

    return x;
}

Пример: 

-1 mod 5 = 4

Полный код базовых операций

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

long long norm(long long x) {
    x %= MOD;

    if (x < 0) {
        x += MOD;
    }

    return x;
}

long long add(long long a, long long b) {
    return norm(a + b);
}

long long sub(long long a, long long b) {
    return norm(a - b);
}

long long mul(long long a, long long b) {
    return norm(a) * norm(b) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;

    cout << add(a, b) << '\n';
    cout << sub(a, b) << '\n';
    cout << mul(a, b) << '\n';

    return 0;
}

Степень по модулю

Часто нужно быстро посчитать: 

a^b mod MOD

Нельзя просто умножать a на себя b раз, если b большое.

Используем быстрое возведение в степень.

если b четное: a^b = (a^(b/2))²
если b нечетное: a^b = a * a^(b-1)

Быстрая степень: идея

Вместо O(b) операций делаем O(log b).

Например: 

2^10 = 1024

Но мы считаем не все 10 умножений подряд, а делим степень пополам.

Это один из самых важных шаблонов в теории чисел.

Код быстрой степени

long long binpow(long long a, long long b) {
    long long res = 1;

    a %= MOD;

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

Полная реализация степени

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

long long binpow(long long a, long long b) {
    long long res = 1;

    a %= MOD;

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;

    cout << binpow(a, b);

    return 0;
}

Input / Output

Input

2 10

Output

1024

Почему нельзя делить обычным способом?

В обычной арифметике: 

10 / 2 = 5

Но по модулю нельзя просто писать: 

a / b % MOD

Потому что деление по модулю работает через обратный элемент.

В модульной арифметике деление заменяется умножением на обратный элемент.

Обратный элемент

Число x называется обратным к a по модулю MOD, если: 

a * x ≡ 1 (mod MOD)

Тогда: 

a / b mod MOD = a * inverse(b) mod MOD

Когда существует обратный элемент?

Обратный элемент для a по модулю m существует, если: 

gcd(a, m) = 1

То есть a и m должны быть взаимно простыми.

Если MOD — простое число, тогда у любого числа от 1 до MOD - 1 есть обратный элемент.

Обратный элемент через малую теорему Ферма

Если MOD — простое число, то: 

inverse(a) = a^(MOD - 2) mod MOD

Поэтому можно использовать binpow: 

long long inv(long long a) {
    return binpow(a, MOD - 2);
}
Это работает только если MOD простое и a не делится на MOD.

Деление по модулю

Чтобы посчитать: 

a / b mod MOD

Пишем: 

a * inv(b) % MOD

Код: 

long long divide(long long a, long long b) {
    return a % MOD * inv(b) % MOD;
}

Полный код: деление по модулю

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

long long binpow(long long a, long long b) {
    long long res = 1;

    a %= MOD;

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

long long inv(long long a) {
    return binpow(a, MOD - 2);
}

long long divide_mod(long long a, long long b) {
    return a % MOD * inv(b) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;

    cout << divide_mod(a, b);

    return 0;
}

Пример обратного элемента

Пусть: 

MOD = 7
a = 3

Нужно найти такое x, что: 

3 * x ≡ 1 (mod 7)

Проверим: 

3 * 5 = 15
15 mod 7 = 1

Значит: 

inverse(3) = 5

Обратный элемент через расширенный Евклид

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

Он ищет: 

a * x + m * y = gcd(a, m)

Если gcd(a, m) = 1, то: 

a * x ≡ 1 (mod m)

Значит x — обратный элемент.

Код inverse через extended gcd

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    long long x1, y1;
    long long d = extgcd(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return d;
}

long long inv_general(long long a, long long m) {
    long long x, y;
    long long d = extgcd(a, m, x, y);

    if (d != 1) {
        return -1;
    }

    x %= m;

    if (x < 0) {
        x += m;
    }

    return x;
}
Если функция вернула -1, значит обратного элемента не существует.

Комбинаторика по модулю

Часто нужно считать: 

C(n, k) mod MOD

Формула: 

C(n, k) = n! / (k! * (n-k)!)

По модулю деление заменяем на обратный элемент.

Факториалы и обратные факториалы

fact[i] = i!
invFact[i] = inverse(i!)

Тогда: 

C(n, k) = fact[n] * invFact[k] % MOD * invFact[n - k] % MOD

Код C(n, k) по модулю

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;
const int N = 1000000;

long long fact[N + 1];
long long invFact[N + 1];

long long binpow(long long a, long long b) {
    long long res = 1;

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

long long inv(long long a) {
    return binpow(a, MOD - 2);
}

void build() {
    fact[0] = 1;

    for (int i = 1; i <= N; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    invFact[N] = inv(fact[N]);

    for (int i = N - 1; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

long long C(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }

    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build();

    int n, k;
    cin >> n >> k;

    cout << C(n, k);

    return 0;
}

Модульное умножение без overflow

Если числа до 10¹⁸, то даже long long * long long может переполниться.

В C++ можно использовать __int128: 

long long mul_mod(long long a, long long b, long long mod) {
    return (__int128)a * b % mod;
}
Это полезно в задачах на большие числа и Miller-Rabin.

Типичные ошибки

  • Писать обычное деление a / b вместо a * inv(b)
  • Забывать брать mod после умножения
  • Получать отрицательный остаток после вычитания
  • Использовать inverse, когда gcd(b, MOD) не равен 1
  • Использовать формулу Ферма, когда MOD не простое
  • Получать overflow в a * b
  • Забывать, что 0 не имеет обратного элемента

Асимптотика

Операция Время
Сложение по модулю O(1)
Вычитание по модулю O(1)
Умножение по модулю O(1)
Быстрая степень O(log b)
Обратный элемент через Ферма O(log MOD)
C(n, k) после build O(1)

Когда что использовать?

нужно сложить → (a + b) % MOD
нужно вычесть → (a - b + MOD) % MOD
нужно умножить → a * b % MOD
нужна степень → binpow(a, b)
нужно делить → a * inv(b) % MOD
нужен C(n,k) → factorial + inverse factorial

Короткий шаблон

const long long MOD = 1000000007;

long long norm(long long x) {
    x %= MOD;

    if (x < 0) {
        x += MOD;
    }

    return x;
}

long long binpow(long long a, long long b) {
    long long res = 1;

    a = norm(a);

    while (b > 0) {
        if (b % 2 == 1) {
            res = res * a % MOD;
        }

        a = a * a % MOD;
        b /= 2;
    }

    return res;
}

long long inv(long long a) {
    return binpow(a, MOD - 2);
}