НОД и НОК

Что такое НОД?

НОД — это наибольший общий делитель.

То есть самое большое число, на которое делятся два числа без остатка.

НОД(a, b) = самое большое число d
такое что a делится на d
и b делится на d

В программировании НОД часто называют:

gcd

Пример НОД

Пусть:

a = 12
b = 18

Делители 12:

1 2 3 4 6 12

Делители 18:

1 2 3 6 9 18

Общие делители:

1 2 3 6

Самый большой общий делитель:

НОД(12, 18) = 6

Что такое НОК?

НОК — это наименьшее общее кратное.

То есть самое маленькое положительное число, которое делится и на a, и на b.

НОК(a, b) = самое маленькое число x
такое что x делится на a
и x делится на b

В программировании НОК часто называют:

lcm

Пример НОК

Пусть:

a = 12
b = 18

Кратные 12:

12 24 36 48 60 ...

Кратные 18:

18 36 54 72 ...

Первое общее кратное:

НОК(12, 18) = 36

Связь НОД и НОК

Для двух положительных чисел:

gcd(a, b) * lcm(a, b) = a * b

Поэтому:

lcm(a, b) = a / gcd(a, b) * b

Лучше писать именно a / gcd(a, b) * b, а не a * b / gcd(a, b), чтобы уменьшить риск overflow.

Наивный способ найти НОД

Можно перебрать все числа от 1 до min(a, b) и найти максимальное, которое делит оба числа.

int gcd_slow(int a, int b) {
    int ans = 1;

    for (int d = 1; d <= min(a, b); d++) {
        if (a % d == 0 && b % d == 0) {
            ans = d;
        }
    }

    return ans;
}

Этот метод простой, но медленный. Его время O(min(a, b)).

Алгоритм Евклида

Быстрый способ найти НОД — алгоритм Евклида.

Главная идея:

gcd(a, b) = gcd(b, a % b)

Пока b не станет 0, заменяем:

a становится b
b становится a % b

Когда b == 0, ответ — a.

Пример алгоритма Евклида

Найдем:

gcd(48, 18)

48 % 18 = 12
gcd(48, 18) = gcd(18, 12)

18 % 12 = 6
gcd(18, 12) = gcd(12, 6)

12 % 6 = 0
gcd(12, 6) = gcd(6, 0)

Ответ:

Рекурсивный gcd

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

    return gcd(b, a % b);
}

Это самый короткий и популярный вариант.

Если числа могут быть большими, используй long long.

Итеративный gcd

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

    return a;
}

Этот вариант не использует рекурсию.

gcd для long long

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    return a;
}

Если числа до 10¹⁸, используй long long.

НОК через НОД

Когда НОД уже умеем считать, НОК считается просто:

lcm(a, b) = a / gcd(a, b) * b

Код:

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

Полная реализация gcd и lcm

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    return a;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;

    cout << gcd(a, b) << '\n';
    cout << lcm(a, b) << '\n';

    return 0;
}

Input / Output

Input

12 18

Output

6
36

Встроенная функция C++

В C++ уже есть готовая функция:

__gcd(a, b)

Пример:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    cout << __gcd(a, b);

    return 0;
}

На олимпиадах часто используют __gcd. Но алгоритм Евклида лучше понимать и уметь писать самому.

std::gcd и std::lcm

В C++17 есть:

std::gcd(a, b)
std::lcm(a, b)

Они находятся в header:

#include <numeric>

Но с bits/stdc++.h они тоже обычно доступны.

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;

    cout << gcd(a, b) << '\n';
    cout << lcm(a, b) << '\n';

    return 0;
}

НОД нескольких чисел

Если дан массив, НОД всех чисел можно считать постепенно:

ans = a[1]
ans = gcd(ans, a[2])
ans = gcd(ans, a[3])
...

long long ans = a[0];

for (int i = 1; i < n; i++) {
    ans = gcd(ans, a[i]);
}

Код: НОД массива

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long ans = a[0];

    for (int i = 1; i < n; i++) {
        ans = gcd(ans, a[i]);
    }

    cout << ans;

    return 0;
}

НОК нескольких чисел

НОК массива тоже считается постепенно:

ans = a[1]
ans = lcm(ans, a[2])
ans = lcm(ans, a[3])
...

long long ans = a[0];

for (int i = 1; i < n; i++) {
    ans = lcm(ans, a[i]);
}

НОК может очень быстро стать большим. Поэтому следи за overflow.

gcd и отрицательные числа

Обычно НОД считают положительным. Поэтому можно брать модуль:

a = abs(a);
b = abs(b);

Код:

long long gcd(long long a, long long b) {
    a = abs(a);
    b = abs(b);

    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    return a;
}

Что если одно число равно 0?

Правила:

gcd(a, 0) = a
gcd(0, b) = b
gcd(0, 0) = 0

Для НОК:

lcm(a, 0) = 0
lcm(0, b) = 0

Поэтому безопасный lcm:

long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) {
        return 0;
    }

    return abs(a / gcd(a, b) * b);
}

Взаимно простые числа

Два числа называются взаимно простыми, если их НОД равен 1.

if (gcd(a, b) == 1) {
    cout << "YES";
}

Пример:

gcd(8, 15) = 1

Значит 8 и 15 взаимно простые.

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

Расширенный Евклид находит такие числа x и y, что:

a * x + b * y = gcd(a, b)

Это нужно для:

линейных диофантовых уравнений
обратного элемента по модулю
теории чисел

Код расширенного Евклида

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    long long x1, y1;
    long long d = extgcd(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return d;
}

Пример расширенного Евклида

Пусть:

a = 30
b = 18

НОД:

gcd(30, 18) = 6

Можно найти:

x = -1
y = 2

Проверка:

30 * (-1) + 18 * 2 = 6

Полный код расширенного Евклида

#include <bits/stdc++.h>
using namespace std;

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    long long x1, y1;
    long long d = extgcd(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;

    long long x, y;
    long long d = extgcd(a, b, x, y);

    cout << d << '\n';
    cout << x << ' ' << y << '\n';

    return 0;
}

Типичные задачи с gcd

найти НОД двух чисел
найти НОК двух чисел
найти НОД массива
проверить, являются ли числа взаимно простыми
сократить дробь
найти период
решить уравнение вида ax + by = c

Сокращение дроби

Чтобы сократить дробь:

a / b

нужно поделить числитель и знаменатель на их НОД.

long long d = gcd(a, b);

a /= d;
b /= d;

Пример:

12 / 18 = 2 / 3

Типичные ошибки

Думать, что НОД — это меньшее число
Путать НОД и НОК
Писать медленный перебор вместо Евклида
Забыть, что gcd(a, 0) = a
Считать lcm как a * b / gcd и получить overflow
Использовать int, когда нужен long long
Не брать abs для отрицательных чисел

Асимптотика

Метод	Время	Память
Наивный НОД	O(min(a, b))	O(1)
Алгоритм Евклида	O(log min(a, b))	O(1)
Расширенный Евклид	O(log min(a, b))	O(log min(a, b))

Алгоритм Евклида очень быстрый, поэтому его можно спокойно использовать много раз.

Как думать на задачах?

1. Нужно найти общий делитель? → gcd
2. Нужно общее кратное? → lcm
3. Нужно сократить дробь? → gcd
4. Нужно проверить взаимную простоту? → gcd == 1
5. Нужно ax + by = c? → extended gcd
6. Есть несколько чисел? → считаем постепенно

Короткий шаблон

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    return abs(a);
}

long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) {
        return 0;
    }

    return abs(a / gcd(a, b) * b);
}