E005. Extended Euclidean algorithm
Источник: e-maxx.ru/algo, страница PDF 18.
В то время как "обычный" Euclidean algorithm просто находит наибольший общий делитель двух чисел
и
,
Extended Euclidean algorithm находит помимо НОД также коэффициенты
и
такие, что: Т.е. он находит коэффициенты, с помощью которых НОД двух чисел выражается через сами эти числа.
Algorithm
Внести вычисление этих коэффициентов в Euclidean algorithm несложно, достаточно вывести формулы, по которым
они меняются при переходе от пары
к паре
(знаком процента мы обозначаем взятие остатка
от деления).
Итак, пусть мы нашли Solution
задачи для новой пары
:
и хотим получить Solution
для нашей пары
:
Для этого преобразуем величину
:
Подставим это в приведённое выше выражение с
и
и получим: и, выполняя перегруппировку слагаемых, получаем:
Сравнивая это с исходным выражением над неизвестными
и
, получаем требуемые выражения:
Implementation
int gcd (int a, int b, int & x, int & y) {if (a == 0) {x = 0; y = 1;
return b;}
int x1, y1;int d = gcd (b%a, a, x1, y1);x = y1 - (b / a) * x1;
y = x1;
return d;} Это рекурсивная функция, которая по-прежнему returns значение НОД от чисел
и
, но помимо этого —
также искомые коэффициенты
и
в виде параметров функции, передающихся по ссылкам.
База рекурсии — случай
. Тогда НОД равен
, и, очевидно, требуемые коэффициенты
и
равны
и
соответственно. В остальных случаях работает обычное Solution, а коэффициенты пересчитываются по вышеописанным формулам. Extended Euclidean algorithm в такой реализации работает корректно даже для отрицательных чисел.
References
● Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Algorithmы: Построение и
анализ [2005]
C# solution
auto-draft, review before submitusing System;
using System.Collections.Generic;
using System.Linq;
public static class AlgorithmDraft
{
// Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
int gcd (int a, int b, int & x, int & y) {
if (a == 0) {
x = 0; y = 1;
return b;
}
int x1, y1;
int d = gcd (b%a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
}C++ solution
matched/originalint gcd (int a, int b, int & x, int & y) {
if (a == 0) {
x = 0; y = 1;
return b;
}
int x1, y1;
int d = gcd (b%a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}Java solution
auto-draft, review before submitimport java.util.*;
import java.math.*;
public class AlgorithmDraft {
// Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
int gcd (int a, int b, int & x, int & y) {
if (a == 0) {
x = 0; y = 1;
return b;
}
int x1, y1;
int d = gcd (b%a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
}Материал разбит как Algorithmическая Task: изучить постановку, понять асимптотику и реализовать Algorithm на выбранном языке.
Vacancies for this task
Active vacancies with overlapping task tags are shown.