НОД. Алгоритм Евклида: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 1: Строка 1:
== Ссылки на задачи ==
long long gcd(long long a, long long b) {
* [http://acm.timus.ru/problem.aspx?num=1053 Timus #1053 — Pinocchio]
    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;
}


== Ссылки ==
== Ссылки ==
* [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://brestprog.neocities.org/lections/gcd.html brestprog.neocities.org — НОД. НОК. Алгоритм Евклида]
:* [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://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел]
:* [https://brestprog.by/topics/gcd/ brestprog.by — НОД. НОК. Алгоритм Евклида]
* [http://algorithmica.org/ru/euclid algorithmica.org — Алгоритм Евклида]
:* [http://algorithmica.org/tg/number-theory algorithmica.org — Теория чисел]
* [http://algorithmica.org/ru/reciprocal algorithmica.org — Обратный элемент по модулю]
:* [http://algorithmica.org/ru/euclid algorithmica.org — Алгоритм Евклида]
* [http://informatics.mccme.ru/course/view.php?id=17 informatics.mccme.ru — Курс «Арифметика и числовые алгоритмы» — часть 2]
:* [http://algorithmica.org/ru/reciprocal algorithmica.org — Обратный элемент по модулю]
* [http://github.com/indy256/codelibrary/blob/master/java/src/Euclid.java CodeLibrary — Euclidean algorithm. GCD, LCM, modular inverse, Chinese remainder theorem]
:* [https://usaco.guide/adv/extend-euclid?lang=cpp usaco.guide — Extended Euclidean Algorithm]
* [http://github.com/ADJA/algos/blob/master/NumberTheory/DiophantineEquation.cpp Algos — Solving Diophantine equations in form of a*x+b*y=c]
Код:
:* [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:Арифметические алгоритмы]]

Версия от 20:20, 21 апреля 2021

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;
}

Ссылки

Теория:

Код:

Задачи:

Источник — https://acm.khpnets.info/w39/index.php?title=НОД._Алгоритм_Евклида&oldid=2671