E005. Расширенный алгоритм Евклида

emaxx algorithm

#algorithm#emaxx#math#number-theory

Task

Источник: e-maxx.ru/algo, страница PDF 18.

В то время как "обычный" алгоритм Евклида просто находит наибольший общий делитель двух чисел

и

,

расширенный алгоритм Евклида находит помимо НОД также коэффициенты

и

такие, что: Т.е. он находит коэффициенты, с помощью которых НОД двух чисел выражается через сами эти числа.

Алгоритм

Внести вычисление этих коэффициентов в алгоритм Евклида несложно, достаточно вывести формулы, по которым

они меняются при переходе от пары

к паре

(знаком процента мы обозначаем взятие остатка

от деления).

Итак, пусть мы нашли решение

задачи для новой пары

и хотим получить решение

для нашей пары

Для этого преобразуем величину

Подставим это в приведённое выше выражение с

и

и получим: и, выполняя перегруппировку слагаемых, получаем:

Сравнивая это с исходным выражением над неизвестными

и

, получаем требуемые выражения:

Реализация

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;

} Это рекурсивная функция, которая по-прежнему возвращает значение НОД от чисел

и

, но помимо этого —

также искомые коэффициенты

и

в виде параметров функции, передающихся по ссылкам.

База рекурсии — случай

. Тогда НОД равен

, и, очевидно, требуемые коэффициенты

и

равны

и

соответственно. В остальных случаях работает обычное решение, а коэффициенты пересчитываются по вышеописанным формулам. Расширенный алгоритм Евклида в такой реализации работает корректно даже для отрицательных чисел.

Литература

● Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и

анализ [2005]

C# solution

auto-draft, review before submit

using 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/original

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

Java solution

auto-draft, review before submit

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

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.