Определения
Если два целых числа \(a\) и \(b\) при делении на \(m\) дают одинаковые остатки, то они называются сравнимыми (или равноостаточными) по модулю числа \(m\).
Сравнимость чисел \(a\) и \(b\) записывается в виде формулы (сравнения):
\(a \equiv b \; (\mathrm{mod} \; m)\)
или
\(a \; \mathrm{mod} \; m = b \; \mathrm{mod} \; m\)
Число \(m\) называется модулем сравнения.
Определение сравнимости чисел \(a\) и \(b\) по модулю \(m\) равносильно любому из следующих утверждений:
- Разность чисел \(a\) и \(b\) делится на \(m\) без остатка:
\((a - b) \; \mathrm{mod} \; m = 0\)
- Число \(a\) может быть представлено в виде:
\(a = b + k \cdot m\),
где \(k\) — некоторое целое число.
Например, числа \(32\) и \(-10\) сравнимы по модулю \(7\), так как оба числа при делении на \(7\) дают остаток \(4\):
\(32 = 7 \cdot 4 + 4\)
\(-10 = 7 \cdot (-2) + 4\)
Также числа \(32\) и \(-10\) сравнимы по модулю \(7\), так как их разность \(32 - (-10) = 42\) делится на \(7\) и к тому же имеет место представление \(32 = -10 + 7 \cdot 6\).
Сложение, вычитание и умножение по модулю
В некоторых задачах фигурирует условие следующего вида: «выведите остаток от деления ответа на \(1000000007\)» или «выведите ответ по модулю \(1000000007\)». Это вовсе не значит, что вам нужно посчитать ответ обычным способом и вывести \(ans \; \% \; 1000000007\). Ответ в таких задачах часто настолько огромен, что его сложно представить даже с помощью длинной арифметики. Для их решения нужно вносить изменения во все промежуточные вычисления.
Можно сказать, что в таких задачах мы оперируем не числами, а их остатками от деления на \(1000000007\). Это возможно благодаря следующим свойствам вычислений с остатком:
\((a + b) \; \mathrm{mod} \; m = ((a \; \mathrm{mod} \; m) + (b\; \mathrm{mod} \; m)) \; \mathrm{mod} \; m\)
\((a - b) \; \mathrm{mod} \; m = ((a \; \mathrm{mod} \; m) - (b\; \mathrm{mod} \; m)) \; \mathrm{mod} \; m\)
\((ab) \; \mathrm{mod} \; m = ((a \; \mathrm{mod} \; m) \cdot (b\; \mathrm{mod} \; m)) \; \mathrm{mod} \; m\)
Таким образом, мы можем выполнять три важнейшие математические операции, даже не зная точных значений чисел, только их остатки от деления на заданное число (модуль).
Возведение в степень по модулю
Часто бывает нужно эффективно вычислить значение \(x^n \; \mathrm{mod} \; m\). Это можно сделать за время \(O(\log n)\), воспользовавшись следующим рекуретным соотношением:
\(x^n = \begin{cases} 1 & n = 0\\ x^\frac{n}2 \cdot x^\frac{n}2 & n \; четно\\x^{n-1} \cdot x & n \; нечетно \end{cases}\)
Например, для вычисления \(x^{100}\) мы сначала вычисляем \(x^{50}\), а затем пользуемся формулой \(x^{100} = x^{50} \cdot x^{50}\). Далее для вычисления \(x^{50}\) мы сначала вычисляем \(x^{25}\) и т. д. Поскольку при четном \(n\) показатель степень уменьшается вдвое, это вычисление занимает время \(O(\log n)\).
Алгоритм реализуется следующей функцией:
def modpow(x, n, m):
res = 1
while n > 0:
if n % 2 == 1:
res = res * x % m
x = x * x % m
n //= 2
return res
Стоит отметить, что бинарное возведение в степень по модулю уже реализовано в языке Python в виде функции pow.
Деление по модулю
К сожалению, деление по модулю не так легко адаптируется, как другие арифметические операции.
С делением по модулю связана одна особенность. Чтобы операция \(\frac{a}b \; \mathrm{mod} \; m\) имела смысл, необходимо, чтобы числа \(b\) и \(m\) были взаимнопростыми. Если модуль \(m\) — простое число, он является взаимнопростым со всеми числами по модулю \(m\), то есть, делить можно на все числа. Но если модуль составной, то операция деления имеет смысл лишь для некоторых чисел, и определяется значительно сложнее. На практике считается, что делить можно только по простому модулю.
Деление по модулю определяется через умножение следующим образом:
\(\frac{a}b \; \mathrm{mod} \; m = (a \cdot \frac1{b}) \; \mathrm{mod} \; m = ab^{-1} \; \mathrm{mod} \; m\)
Ключевую роль играет значение \(b^{-1}\), называющееся обратным элементом по модулю. Оно никак не связано с классическим понятием обратного числа, хотя бы тем, что всегда является целым. Для обратного элемента должно выполняться следующее условие:
\(x \cdot x^{-1} \; \mathrm{mod} \; m = 1\)
Например, обратным элементом по модулю \(1000000007\) для числа \(2\) является число \(500000004\), так как \(2 \cdot 500000004 \; \mathrm{mod} \; 1000000007 = 1\). Следовательно, по модулю \(1000000007\) делению на \(2\) соответствует умножение на \(500000004\).
Алгоритм нахождения обратного элемента в поле по простому модулю выражается следующей формулой:
\(x^{-1} \; \mathrm{mod} \; m = x^{m-2} \; \mathrm{mod} \; m\)
Стоит заметить что из-за использования бинарного возведения в степень, деление по модулю имеет сложность \(O(\log m)\), тогда как все остальные арифметические операции по модулю работают за \(O(1)\).