Алгоритм Евкліда для обчислення найбільшого спільного дільника

Маючи два невід'ємні цілі числа $a$ і $b$, ми повинні знайти їхній НСД (найбільший спільний дільник), тобто найбільше число, яке є дільником і $a$, і $b$. Зазвичай його позначають $\gcd(a, b)$. Математично він означається так:

$$\gcd(a, b) = \max \{k > 0 : (k \mid a) \text{ and } (k \mid b) \}$$

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

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

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

Уперше алгоритм був описаний у «Началах» Евкліда (близько 300 року до н. е.), але можливо, що алгоритм має навіть давніше походження.

Коли підходить цей алгоритм?

• Чи потрібно знайти лише найбільший спільний дільник (або, через нього, найменше спільне кратне) двох чи кількох чисел?
• Чи вам не потрібні коефіцієнти Безу $x, y$ у $ax + by = \gcd(a,b)$? (якщо потрібні → Розширений алгоритм Евкліда)
• Якщо ви розв'язуєте рівняння $ax + by = c$ у цілих числах — (→ Лінійні діофантові рівняння)?

Алгоритм

Спочатку алгоритм Евкліда був сформульований так: віднімаємо менше число від більшого, доки одне з чисел не стане нулем. Справді, якщо $g$ ділить $a$ і $b$, то воно ділить і $a-b$. З іншого боку, якщо $g$ ділить $a-b$ і $b$, то воно ділить і $a = b + (a-b)$, а це означає, що множини спільних дільників $\{a, b\}$ і $\{b,a-b\}$ збігаються.

Зауважимо, що $a$ залишається більшим числом доти, доки від нього не віднімуть $b$ принаймні $\left\lfloor\frac{a}{b}\right\rfloor$ разів. Тому, щоб прискорити процес, $a-b$ замінюють на $a-\left\lfloor\frac{a}{b}\right\rfloor b = a \bmod b$. Тоді алгоритм формулюється надзвичайно просто:

$$\gcd(a, b) = \begin{cases}a,&\text{if }b = 0 \\ \gcd(b, a \bmod b),&\text{otherwise.}\end{cases}$$

Реалізація

C++

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

Python

def gcd(a: int, b: int) -> int:
    if b == 0:
        return a
    return gcd(b, a % b)

TypeScript

function gcd(a: number, b: number): number {
  if (b === 0) return a;
  return gcd(b, a % b);
}

Go

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

Скориставшись тернарним оператором у C++, ми можемо записати це одним рядком.

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

І нарешті, ось нерекурсивна реалізація:

C++

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

Python

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

TypeScript

function gcd(a: number, b: number): number {
  while (b) {
    [a, b] = [b, a % b];
  }
  return a;
}

Go

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

Зауважимо, що більшість мов постачають функцію НСД у своїй стандартній бібліотеці: у C++17 є std::gcd, у Python — math.gcd, а в Go — big.Int.GCD.

Часова складність

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

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

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

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

Інший спосіб оцінити складність — помітити, що $a \bmod b$ для випадку $a \geq b$ принаймні у $2$ рази менше за $a$, тож більше число зменшується принаймні вдвічі на кожній ітерації алгоритму. Застосовуючи це міркування до випадку, коли ми обчислюємо НСД набору чисел $a_1,\dots,a_n \leq C$, це також дозволяє нам оцінити загальний час роботи як $O(n + \log C)$, а не $O(n \log C)$, оскільки кожна нетривіальна ітерація алгоритму зменшує поточного кандидата на НСД принаймні у $2$ рази.

Найменше спільне кратне

Обчислення найменшого спільного кратного (зазвичай позначається НСК) можна звести до обчислення НСД за допомогою такої простої формули:

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

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

Ось можлива реалізація, яка хитро уникає переповнень цілих чисел, спочатку поділивши $a$ на НСД:

C++

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

Python

def lcm(a: int, b: int) -> int:
    return a // gcd(a, b) * b

TypeScript

function lcm(a: number, b: number): number {
  return (a / gcd(a, b)) * b;
}

Go

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

Бінарний НСД

Алгоритм бінарного НСД є оптимізацією звичайного алгоритму Евкліда.

Повільна частина звичайного алгоритму — це операції за модулем. Хоча ми сприймаємо операції за модулем як $O(1)$, вони набагато повільніші за простіші операції на кшталт додавання, віднімання чи бітових операцій. Тому було б краще їх уникати.

Виявляється, що можна сконструювати швидкий алгоритм НСД, який уникає операцій за модулем. Він ґрунтується на кількох властивостях:

• Якщо обидва числа парні, то ми можемо винести двійку з обох і обчислити НСД решти чисел: $\gcd(2a, 2b) = 2 \gcd(a, b)$.
• Якщо одне з чисел парне, а інше непарне, то ми можемо прибрати множник 2 з парного: $\gcd(2a, b) = \gcd(a, b)$, якщо $b$ непарне.
• Якщо обидва числа непарні, то віднімання одного числа від іншого не змінить НСД: $\gcd(a, b) = \gcd(b, a-b)$

Використовуючи лише ці властивості та деякі швидкі бітові функції з GCC, ми можемо реалізувати швидку версію:

int gcd(int a, int b) {
    if (!a || !b)
        return a | b;
    unsigned shift = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);
    do {
        b >>= __builtin_ctz(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    return a << shift;
}

Зверніть увагу, що така оптимізація зазвичай не потрібна, і більшість мов програмування вже мають функцію НСД у своїх стандартних бібліотеках. Наприклад, у C++17 є така функція std::gcd у заголовку numeric.

Задачі для практики

• CSAcademy - Greatest Common Divisor
• Codeforces 1916B - Two Divisors

Відеоматеріали