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

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

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

или

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

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

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

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

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

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

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

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

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

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

Значит, по определению сравнимости, , что и требовалось доказать.

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

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

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

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

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

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). Однако существует два момента, которые нужно всегда учитывать для избежания ошибок:

  • Взятие отрицательных чисел по модулю. Согласно математическому определению, , так как . К сожалению, оператор % в С++ реализован иначе, и по его версии . Это может привести к ошибкам в вычислениях, поэтому нужно вручную обрабатывать такие случаи следующим образом:

    long long result;
    //...
    result -= x;
    result %= MOD;
    if (result < 0) result += MOD;   //Теперь всё должно работать.
    
  • Переполнение типа int при умножении. Не рекомендуется использовать тип int для хранения чисел по модулю 1000000007, так как при умножении двух таких чисел результат может достигать , что вызывет переполнение. При умножении чисел по модулю всегда используйте тип long long!

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

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

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

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

Простой рекурсивный вариант на 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;
    }
}

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

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

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

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

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

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

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

Например, обратным элементов в поле по модулю для числа является число , так как . Следовательно, в поле по модулю делению на соответствует умножение на

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

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

Реализация на 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;
}

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