НОД. Алгоритм Евклида: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 17: | Строка 17: | ||
y = x1 - a / b * y1; | y = x1 - a / b * y1; | ||
return d; | return d; | ||
} | |||
long long inv(long long a, long long mod) { | |||
long long x, y; | |||
return a && gcdex(a, mod, x, y) == 1 ? (x % mod + mod) % mod : 0; | |||
} | } | ||
Текущая версия от 16:09, 14 мая 2023
long long gcd(long long a, long long b) {
return b ? gcd(b, a % b) : a;
}
long long lcm(long long a, long long b) {
return a / gcd(a, b) * b;
}
long long gcdex(long long a, long long b, long long &x, long long &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
long long x1, y1, d = gcdex(b, a % b, x1, y1);
x = y1;
y = x1 - a / b * y1;
return d;
}
long long inv(long long a, long long mod) {
long long x, y;
return a && gcdex(a, mod, x, y) == 1 ? (x % mod + mod) % mod : 0;
}
Ссылки
Теория:
- e-maxx.ru — Алгоритм Евклида нахождения НОД (наибольшего общего делителя)
- e-maxx.ru — Расширенный алгоритм Евклида
- e-maxx.ru — Обратный элемент в кольце по модулю
- e-maxx.ru — Диофантовы уравнения с двумя неизвестными: AX+BY=C
- neerc.ifmo.ru — Наибольший общий делитель
- brestprog.by — НОД. НОК. Алгоритм Евклида
- algorithmica.org — Теория чисел
- algorithmica.org — Алгоритм Евклида
- algorithmica.org — Обратный элемент по модулю
- usaco.guide — Extended Euclidean Algorithm
Код:
Задачи: