Алгоритм Евкліда знаходження НСД

Дано два цілих невід'ємних числа $a$ і $b$. Потрібно знайти їх найбільший спільний дільник, тобто найбільше таке число, яке є дільником одночасно і $a$, і $b$. На англійській мові "найбільший спільний дільник" пишеться "greatest common divisor", і позначається як ${\rm gcd}$:

$${\rm gcd}(a,b) = \max_{k=1 \ldots \infty \ :\ k|a \ \&\ k|b} k$$

(тут символом "$|$" позначено ділимість, тобто "$k|a$" означає "$k$ націло ділить $a$")

Коли одне з чисел рівне нулю, а інше відмінне від нуля, тоді їх найбільшим спільним дільником, згідно визначенню, буде друге число. Коли обидва числа рівні нулю, результат не визначений (підійде будь-яке нескінченно велике число), тому покладемо у цьому випадку найбільший спільний дільник рівним нулю. Тому можна говорити про таке правило: якщо одне з чисел рівне нулю, то їх найбільший спільним дільник рівний другому числу.

Алгоритм Евкліда, що розглядається нижче, розв'язує задачу знаходження найбільшого спільного дільника двох чисел $a$ і $b$ за $O(\log \min(a,b))$.

Даний алгоритм був вперше описаний у книзі Евкліда "Начала" (близько 300 р. до н.е).

Алгоритм

Сам алгоритм надзвичайно простий і описується наступною формулою:

$${\rm gcd}(a,b) = \begin{cases} a, & \text{якщо }b=0 \cr {\rm gcd} (b, a\ {\rm mod}\ b), & \text{інакше} \end{cases}$$

Реалізація

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}

Використовуючи тернарний умовний оператор C++, алгоритм можна записати ще коротше:

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

Оптимальніша нерекурсивна форма алгоритму:

int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

Доведення коректності

Спочатку зауважимо, що при кожній ітерації алгоритму Евкліда його другий аргумент завжди зменшується, а отже, оскільки він невід'ємний, алгоритм Евкліда завжди завершується.

Для доведення коректності нам необхідно показати, що ${\rm gcd}(a,b) = {\rm gcd} (b, a\ {\rm mod}\ b)$ для будь-яких $a \ge 0, b > 0$.

Покажемо, що величина, що стоїть в лівій частини рівності, ділиться на величину у правій, а та, шо стоїть у правій - ділиться на величину у лівій. Очевидно, це буде означати, що ліва і права частини збігаються, що і доведе коректність алгоритму Евкліда.

Позначимо $d = {\rm gcd}(a,b)$. Значить, за визначенням, $d|a$ і $d|b$.

Далі, розкладемо залишок від ділення $a$ на $b$ через їх частку:

$$a\ {\rm mod}\ b = a - b \left\lfloor \frac{a}{b} \right\rfloor$$

Звідси випливає:

$$d\ |\ (a\ {\rm mod}\ b)$$

Отже, згадуючи твердження $d|b$, отримуємо систему:

$$\begin{cases} d\ |\ b, \cr d\ |\ (a\ {\rm mod}\ b) \end{cases}$$

Скористаємося тепер наступним простим фактом: якщо для якихось трьох чисел $p,q,r$ виконуються: $p|q$ і $p|r$, то виконується і: $p\ |\ {\rm gcd}(q,r)$. У нашій ситуації отримуємо:

$$d\ |\ {\rm gcd}(b, a\ {\rm mod}\ b)$$

Або, підставляючи замість $d$ його визначення як ${\rm gcd}(a,b)$, отримуємо:

$${\rm gcd}(a,b)\ |\ {\rm gcd}(b, a\ {\rm mod}\ b)$$

Отже, ми здійснили половину доведення: показали, що ліва частина ділить праву. Друга половина доведення аналогічна.

Час роботи

Час роботи алгоритму оцінюється теоремою Ламе, яка встановлює дивовижний зв'язок алгоритму Евкліда і послідовності Фібоначчі:

Якщо $a > b \ge 1$ і $b < F_n$ для деякого $n$, то алгоритм Евкліда виконає не більше $n-2$ рекурсивних викликів.

Більше того, можна показати, що верхня межа цієї теореми - оптимальна. При $a = F_n, b = F_{n-1}$ буде виконано саме $n-2$ рекурсивних викликів. Іншими словами, послідовні числа Фібоначчі - найгірші вхідні дані для алгоритму Евкліда.

Враховуючи, що числа Фібоначчі ростуть експоненціально (як константа в степені $n$), отримуємо, що алгоритм Евкліда виконується за $O(\log \min(a,b))$ операцій множення.

Застосування

НСК

Обчислення найменшого спільного кратного (least common multiplier, lcm) зводиться до обчислення $\rm gcd$ наступним простим твердженням:

$${\rm lcm}(a,b) = \frac{ a \cdot b }{ {\rm gcd}(a,b) }$$

Таким чином, обчислення НСК також можна здійснити за допомогою алгоритму Евкліда, з тією ж асимптотикою:

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

Зауваження

Варто спочатку поділити на $\rm gcd$, а тільки потім помножити на $b$, оскільки це допоможе уникнути переповнення типу у деяких випадках.

Задачі

• CodeChef - FLOW016 - GCD and LCM