НОД. Алгоритм Евклида: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылки на задачи == * [http://acm.timus.ru/problem.aspx?num=1053 Timus #1053 — Pinocchio] == Ссылки == * [http://e-maxx.ru/algo/eucl…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
== | 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; | |||
} | |||
== Ссылки == | == Ссылки == | ||
* [http://e-maxx.ru/algo/euclid_algorithm e-maxx.ru — Алгоритм Евклида нахождения НОД (наибольшего общего делителя)] | Теория: | ||
* [http://e-maxx.ru/algo/extended_euclid_algorithm e-maxx.ru — Расширенный алгоритм Евклида] | :* [http://e-maxx.ru/algo/euclid_algorithm e-maxx.ru — Алгоритм Евклида нахождения НОД (наибольшего общего делителя)] | ||
* [http://e-maxx.ru/algo/reverse_element e-maxx.ru — Обратный элемент в кольце по модулю] | :* [http://e-maxx.ru/algo/extended_euclid_algorithm e-maxx.ru — Расширенный алгоритм Евклида] | ||
* [http://e-maxx.ru/algo/diofant_2_equation e-maxx.ru — Диофантовы уравнения с двумя неизвестными: AX+BY=C] | :* [http://e-maxx.ru/algo/reverse_element e-maxx.ru — Обратный элемент в кольце по модулю] | ||
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B8%D0%B9_%D0%BE%D0%B1%D1%89%D0%B8%D0%B9_%D0%B4%D0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C neerc.ifmo.ru — Наибольший общий делитель] | :* [http://e-maxx.ru/algo/diofant_2_equation e-maxx.ru — Диофантовы уравнения с двумя неизвестными: AX+BY=C] | ||
* [http:// | :* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B8%D0%B9_%D0%BE%D0%B1%D1%89%D0%B8%D0%B9_%D0%B4%D0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C neerc.ifmo.ru — Наибольший общий делитель] | ||
* [ | :* [https://brestprog.by/topics/gcd/ brestprog.by — НОД. НОК. Алгоритм Евклида] | ||
* [http://github.com/ADJA/algos/blob/master/NumberTheory/DiophantineEquation.cpp | :* [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел] | ||
:* [http://algorithmica.org/ru/euclid algorithmica.org — Алгоритм Евклида] | |||
:* [http://algorithmica.org/ru/reciprocal algorithmica.org — Обратный элемент по модулю] | |||
:* [https://usaco.guide/adv/extend-euclid?lang=cpp usaco.guide — Extended Euclidean Algorithm] | |||
Код: | |||
:* [https://github.com/indy256/codelibrary/blob/master/cpp/numbertheory/euclid.cpp codelibrary/cpp/numbertheory/euclid.cpp] | |||
:* [http://github.com/ADJA/algos/blob/master/NumberTheory/DiophantineEquation.cpp algos/NumberTheory/DiophantineEquation.cpp] | |||
Задачи: | |||
:* [http://informatics.mccme.ru/course/view.php?id=17 informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 2] | |||
:* [http://acm.timus.ru/problem.aspx?num=1053 Timus #1053 — Pinocchio] | |||
[[Category:Арифметические алгоритмы]] | [[Category:Арифметические алгоритмы]] | ||
Текущая версия от 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
Код:
Задачи: