Евклидов (НОД)

Введение

Даны два неотрицательных целых числа $a$ и $b$ , мы хотим найти их наибольший общий делитель (НОД), то есть наибольшее положительное целое число, которое делит оба числа.

Например:

$\text{GCD}(2, 4) = 2$
$\text{GCD}(6, 9) = 3$

Внешние задачи

Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:

CODEFORCESRow GCD

Rating: 1600

\text{GCD}(7, 10) = 1

GCD (7, 10) = 1

Формально,

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

Здесь символ $\mid$ означает делимость. Например, $k \mid a$ означает, что $k$ делит $a$ .

Алгоритм

Алгоритм Евклида основан на нескольких простых наблюдениях.

Наблюдение 1

\text{GCD}(x, 0) = \text{GCD}(0, x) = x

Если одно из чисел равно нулю, то НОД — это другое число.

Наблюдение 2

\text{GCD}(a, b) = \text{GCD}(b, a)

Порядок чисел не имеет значения.

Наблюдение 3

Предположим, что $b \leq a$ . Тогда:

\text{GCD}(a, b) = \text{GCD}(a - b, b)

Действительно, вычитание $b$ из $a$ не изменяет общие делители.

Если повторить это вычитание много раз, мы в итоге получим остаток от деления $a$ на $b$ . Поэтому более быстрая версия:

\text{GCD}(a, b) = \text{GCD}(a \bmod b, b)

Используя эту идею, получаем основную рекурсивную формулу:

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

Реализация

Рекурсивное решение

Итеративное решение

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

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