Модульная арифметика: различия между версиями
м (Добавлена ссылка на статью про нахождение обратного) |
|||
Строка 51: | Строка 51: | ||
О том, как искать обратный по модулю читайте в [[Обратный элемент по модулю|отдельной статье]]. | О том, как искать обратный по модулю читайте в [[Обратный элемент по модулю|отдельной статье]]. | ||
+ | |||
+ | == Код на C++== | ||
+ | <syntaxhighlight lang="C++"> | ||
+ | |||
+ | const int mod = 1e9 + 7; // Поменяйте на тот, который в вашей задаче | ||
+ | template<typename T> | ||
+ | T add(T x) { | ||
+ | return x; | ||
+ | } | ||
+ | |||
+ | template<typename T, typename... Ts> | ||
+ | T add(T x, Ts... y) { | ||
+ | T res = x + add(y...); | ||
+ | if (res >= mod) | ||
+ | res -= mod; | ||
+ | return res; | ||
+ | } | ||
+ | // Конструкция выше позволяет писать add(x, y, z, t, ...) с любым количеством аргументов | ||
+ | |||
+ | template<typename T, typename... Ts> | ||
+ | T sub(T x, Ts... y) { | ||
+ | return add(x, mod - add(y...)); | ||
+ | } | ||
+ | |||
+ | // udd это add, записывающий результат сложения в первый аргумент. | ||
+ | // Старое значение первого аргумента в сумме участвует | ||
+ | template<typename T, typename... Ts> | ||
+ | void udd(T &x, Ts... y) { | ||
+ | x = add(x, y...); | ||
+ | } | ||
+ | |||
+ | |||
+ | template<typename T> | ||
+ | T mul(T x) { | ||
+ | return x; | ||
+ | } | ||
+ | |||
+ | template<typename T, typename... Ts> | ||
+ | T mul(T x, Ts... y) { | ||
+ | return (x * 1ll * mul(y...)) % mod; | ||
+ | } | ||
+ | |||
+ | template<typename T, typename... Ts> | ||
+ | void uul(T &x, Ts... y) { | ||
+ | x = mul(x, y...); | ||
+ | } | ||
+ | |||
+ | int bin(int a, ll deg) { | ||
+ | int r = 1; | ||
+ | while (deg) { | ||
+ | if (deg & 1) | ||
+ | uul(r, a); | ||
+ | deg >>= 1; | ||
+ | uul(a, a); | ||
+ | } | ||
+ | return r; | ||
+ | } | ||
+ | |||
+ | int inv(int x) { | ||
+ | assert(x); | ||
+ | return bin(x, mod - 2); | ||
+ | } | ||
+ | </syntaxhighlight> | ||
{{Автор|Полина Романченко|Romanchenko}} | {{Автор|Полина Романченко|Romanchenko}} | ||
+ | {{Автор|Саша Гришутин|rationalex}} | ||
[[Категория:Конспект]] | [[Категория:Конспект]] | ||
[[Категория:Конспект]] | [[Категория:Конспект]] |
Версия 16:49, 10 февраля 2021
Модульная арифметика
Говоря о теории чисел, мы будем работать с остатками.
Определение:
Остаток от деления $a$ на $b$ —это такое число $0 \le c < b$, что $a = bq + c$ для некоторого $q$.
Выражение $a \equiv b \pmod m$ означает, что остатки от деления $a$ на $m$ и $b$ на $m$ равны. Это выражение читается как «$a$ сравнимо $b$ по модулю $m$».
Еще это можно опрделить так: $a$ сравнимо c $b$ по модулю $m$, если $(a - b)$ делится на $m$.
Все целые числа можно разделить на классы эквивалентности — два числа лежат в одном классе, если они сравнимы по модулю $m$. Говорят, что мы работаем в «кольце остатков по модулю $m$», и в нем ровно $m$ элементов: $0, 1, 2, \cdots, m-1$.
Сложение, вычитение и умножение по модулю определяются довольно интуитивно — нужно выполнить соответствующую операцию и взять остаток от деления.
Некоторые свойства:
- $a \equiv b$, $c \equiv d \Rightarrow a \pm c \equiv b \pm d \mod m$
- $a \equiv b$, $c \equiv d \Rightarrow ac \equiv bd \mod m$
- $a\equiv b \mod m \Rightarrow a^n \equiv b^n \mod m$
Деление по модулю
Поделить одно число $a$ на другое число $b$ в кольце вычетов по модулю $m$ — значит найти такое число $c$, что $cb \equiv a \mod m$. Эта задача уже сложнее, чем сложение и умножение по модулю. Она сводится у нахождению так называемого обратного по модулю к числу $b$.
Обратным к числу $a$ по модулю $m$ называют такое число $a^{-1}$, что $a\cdot a^{-1} \equiv 1 \mod m$.
В том случае, если модуль простой (является простым числом), найти обратный всегда можно, только если исходное число не делится на модуль $m$. Если же модуль — составное число, то обратный элемент к $a$ существует только тогда, когда $(a, m) = 1$, то есть когда $a$ и $m$ взаимнопросты.
Утверждение: (Существование обратного)
Обратный элемент существует только для чисел, взаимно простых с модулем
Доказательство:
Сначала покажем, что для взаимно простого с $m$ числа обратный всегда найдется. Так как мы работаем только с остатками по модулю $m$, то будем считать одним и тем же объектом число и его остаток.
Рассмотрим числа $0\cdot a, 1\cdot a, ... , (m-1)\cdot a$. Поймем, что это различные остатки по модулю $m$. Допустим, есть два одинаковых и это $xa$ и $ya$. Тогда $a(x - y) \equiv 0 \mod m$. Но так как $(a, m) = 1$, то $x - y \equiv 0 \mod m$. Но оба числа $x, y$ лежат на отрезке $[0, m-1]$. Так как их разность сравнима с нулем, то они могут быть только одинаковыми числами, иначе их разность будет находиться в отрезке $[1, m-1]$. Значит, все остатки различны. Так как их $m-1$ штука, то обязательно встретится остаток $1$. То есть найдется $ka \equiv 1 \mod m$ — обратный по модулю $m$ к числу $a$.
Теперь покажем, что для чисел, не взаимно простых с $m$, обратного не существует. Пусть $(a, m) = b > 1$. Тогда если есть обратный, то $aa^{-1} \equiv 1 \mod m$.
$a = bt, \ m = bp$
$bta^{-1}-1=bp \Rightarrow b\left(ta^{-1} - p\right) = 1 \Rightarrow b \mid 1$ — противоречие.
Значит, обратный элемент существует для тех и только тех элементов, которые взаимно просты с модулем $m$.
Если мы нашла обратное к $b$ число, то $ab^{-1} \equiv bcb^{-1} \equiv c \mod m$. То есть умножив $a$ на обратное к $b$ число, мы выполнили деление и нашли искомое $c$.
О том, как искать обратный по модулю читайте в отдельной статье.
Код на C++
const int mod = 1e9 + 7; // Поменяйте на тот, который в вашей задаче
template<typename T>
T add(T x) {
return x;
}
template<typename T, typename... Ts>
T add(T x, Ts... y) {
T res = x + add(y...);
if (res >= mod)
res -= mod;
return res;
}
// Конструкция выше позволяет писать add(x, y, z, t, ...) с любым количеством аргументов
template<typename T, typename... Ts>
T sub(T x, Ts... y) {
return add(x, mod - add(y...));
}
// udd это add, записывающий результат сложения в первый аргумент.
// Старое значение первого аргумента в сумме участвует
template<typename T, typename... Ts>
void udd(T &x, Ts... y) {
x = add(x, y...);
}
template<typename T>
T mul(T x) {
return x;
}
template<typename T, typename... Ts>
T mul(T x, Ts... y) {
return (x * 1ll * mul(y...)) % mod;
}
template<typename T, typename... Ts>
void uul(T &x, Ts... y) {
x = mul(x, y...);
}
int bin(int a, ll deg) {
int r = 1;
while (deg) {
if (deg & 1)
uul(r, a);
deg >>= 1;
uul(a, a);
}
return r;
}
int inv(int x) {
assert(x);
return bin(x, mod - 2);
}
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko
Автор конспекта: Саша Гришутин
По всем вопросам пишите в telegram @rationalex