Математические термины

Во всём последующем материале никак не фигурирует понятие “модуль числа” в привычном смысле (\(\lvert x \rvert\)). Речь идёт о “сравнении по модулю”. Если вы не знакомы с этим понятием, вкратце сравнение по модулю выглядит следующим образом:

\[a \equiv b \pmod{m}.\]

Это читается “\(a\) сравнимо с \(b\) по модулю \(m\)”, и в привычных для информатики терминах обозначает следующее:

\[(a - b) \bmod m = 0\]

или

\[a \bmod m = b \bmod m,\]

где \(\bmod\) - операция взятия остатка от деления.

Поле по модулю

В некоторых задачах фигурирует условие следующего вида: “выведите остаток от деления ответа на 1000000007” или “выведите ответ по модулю 1000000007”. Это вовсе не значит, что вам нужно посчитать ответ обычным способом и вывести ans % 1000000007. Ответ в таких задачах часто настолько огромен, что его сложно представить даже с помощью длинной арифметики. Для их решения нужно вносить изменения во все промежуточные вычисления, чтобы не выйти за границы целочисленного типа.

Можно сказать, что в таких задачах мы оперируем не числами, а их остатками от деления на 1000000007. Это возможно благодаря следующим свойствам вычислений с остатком:

\[(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m \\ (a - b) \bmod m = ((a \bmod m) - (b \bmod m)) \bmod m \\ (ab) \bmod m = ((a \bmod m) * (b \bmod m)) \bmod m\]

Таким образом, мы можем выполнять три важнейшие математические операции, даже не зная точных значений чисел, только их остатки от деления на заданное число (модуль). Деление - отдельная тема, которую мы обсудим позже.

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

Примечание: термин “поле” применим только в том случае, когда модуль - простое число. В противном случае это называется “кольцо”. Отличие заключается в том, что для поля определена операция деления, а для кольца - нет.

Доказательство возможности сложения, вычитания и умножения по модулю

Для начала докажем достаточно очевидное утверждение:

\[\forall n \in \mathbb{Z}: x \bmod m = (x + nm) \bmod m.\]

Доказательство:

\[((x + nm) - x) \bmod m = nm \bmod m = 0\]

Значит, по определению сравнимости, \(\forall n \in \mathbb{Z}: x \equiv x + nm \pmod{m}\), что и требовалось доказать.

Докажем возможность сложения (\(x\) и \(y\) - целые части от деления \(a\) и \(b\) на \(m\) соответственно):

\[(a + b) \bmod m = \\ = (xm + a \bmod m + ym + b \bmod m) \bmod m = \\ = (a \bmod m + b \bmod m + m(x + y)) \bmod m, = \\ = (a \bmod m + b \bmod m) \bmod m,\]

что и требовалось доказать.

Вычитание и умножение доказываются похожим образом:

\[(a - b) \bmod m = \\ = (xm + a \bmod m - ym - b \bmod m) \bmod m = \\ = (a \bmod m - b \bmod m + m(x - y)) \bmod m, = \\ = (a \bmod m - b \bmod m) \bmod m,\] \[(a * b) \bmod m = \\ = ((xm + a \bmod m) * (ym + b \bmod m)) \bmod m = \\ = (a \bmod m * b \bmod m + a \bmod m * ym + b \bmod m * xm + xym^2) \bmod m = \\ = (a \bmod m * b \bmod m + m(a \bmod m * y + b \bmod m * x + xym)) \bmod m = \\ = (a \bmod m * b \bmod m) \bmod m\]

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

В качестве примера, вычислим значение \(10^8!\) по модулю \(10^9 + 7\):

1
2
3
4
5
6
7
8
9
10
11
12

const long long MOD = 1e9 + 7;

long long fact_mod() {
    long long result = 1;

    for (int i = 1; i <= 100000000; i++) {
        result *= i;
        result %= MOD;  //Самая важная строка.
    }

    return result;
}

Как видите, на практике вычисления в поле по модулю отличаются от обычных лишь наличием взятия всех промежуточных результатов по модулю (строка 8). Однако существует два момента, которые нужно всегда учитывать для избежания ошибок:

  • Взятие отрицательных чисел по модулю. Согласно математическому определению, \(-1 \bmod 5 = 4\), так как \(-1 = -1 * 5 + 4\). К сожалению, оператор % в С++ реализован иначе, и по его версии \(-1 \bmod 5 = -1\). Это может привести к ошибкам в вычислениях, поэтому нужно вручную обрабатывать такие случаи следующим образом:

    long long result;
//...
result -= x;
result %= MOD;
if (result < 0) result += MOD;   //Теперь всё должно работать.

  • Переполнение типа int при умножении. Не рекомендуется использовать тип int для хранения чисел по модулю 1000000007, так как при умножении двух таких чисел результат может достигать \(10^{18}\), что вызывет переполнение. При умножении чисел по модулю всегда используйте тип long long!

Возведение в степень по модулю. Бинарное возведение в степень

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

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

\[x^{2n} = x^n * x^n\]

Таким образом засчёт одной операции умножения можно уменьшить степень вдвое. Если же текущая степень нечётная, то можно просто уменьшить её на единицу простым умножением, и получить чётную.

Простой рекурсивный вариант на C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

const long long MOD = 1e9 + 7;

//base ^ p
long long bin_pow(long long base, long long p) {
    if (p == 1) {
        return base;    //Выход из рекурсии.
    }

    if (p % 2 == 0) {
        long long t = bin_pow(base, p / 2);
        return t * t % MOD;
    } else {
        return bin_pow(base, p - 1) * base % MOD;
    }
}

Можно заметить, что в худшем случае на каждом втором вызове функции степень будет уменьшаться вдвое. Значит, время работы алгоритма можно оценить как \(O(\log p)\).

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

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

К сожалению, деление не так легко адаптируется к полю по модулю, как другие арифметические операции. В этом разделе описывается один из способов деления по модулю, но не приводится его доказательство, так как оно значительно усложнило бы эту лекцию.

С делением по модулю связана одна особенность. Чтобы операция \(a/b \bmod m\) имела смысл, необходимо, чтобы числа \(b\) и \(m\) были взаимнопростыми. Если модуль \(m\) - простое число, он является взаимнопростым со всеми числами по модулю \(m\), то есть, делить можно на все числа. Но если модуль составной, то операция деления имеет смысл лишь для некоторых чисел, и определяется значительно сложнее. На практике считается, что делить можно только в поле по простому модулю.

Деление по модулю определяется через умножение следующим образом:

\[{a \over b} \bmod b = (a * {1 \over b}) \bmod m = ab^{-1} \bmod m.\]

Ключевую роль играет значение \(b^{-1}\), называющееся обратный элемент в поле по модулю. Оно никак не связано с классическим понятием обратного числа, хотя бы тем, что всегда является целым (так как в поле по модулю существуют только целые числа). Для обратного элемента должно выполняться следующее условие:

\[(x * x^{-1}) \bmod m = 1.\]

Например, обратным элементов в поле по модулю \(1000000007\) для числа \(2\) является число \(500000004\), так как \((2 * 500000004) \bmod 1000000007 = 1\). Следовательно, в поле по модулю \(1000000007\) делению на \(2\) соответствует умножение на \(500000004\)

Алгоритм нахождения обратного элемента в поле по простому модулю достаточно прост (в реализации) и выражается следующей формулой:

\[x^{-1} \bmod m = x^{m - 2} \bmod m\]

Как можно заметить, число \(x\) возводится в достаточно большую степень, и линейный алгоритм в этой ситуации не подойдёт. Вот и пример необходимости использования бинарного возведения в степень по модулю.

Реализация на C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const long long MOD = 1e9 + 7;

//base ^ p
long long bin_pow(long long base, long long p) {
    if (p == 1) {
        return base;
    }

    if (p % 2 == 0) {
        long long t = bin_pow(base, p / 2);
        return t * t % MOD;
    } else {
        return bin_pow(base, p - 1) * base % MOD;
    }
}

long long inverse_element(long long x) {
    return bin_pow(x, MOD - 2);
}

//(a / b) mod m
long long divide(long long a, long long b) {
    return a * inverse_element(b) % MOD;
}

Стоит заметить что из-за использования бинарного возведения в степень, деление по модулю имеет сложность \(O(\log m)\), тогда как все остальные арифметические операции по модулю работают за \(O(1)\).