НОД және НОК

НОД деген не?

НОД — ең үлкен ортақ бөлгіш.

Яғни екі санды да қалдықсыз бөлетін ең үлкен сан.

НОД(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 * b / gcd(a, b) деп жазғаннан гөрі, a / gcd(a, b) * 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 нөл болғанға дейін ауыстырамыз:

a орнына b келеді
b орнына a % b келеді

b == 0 болғанда answer — 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;
}

Бұл вариант рекурсия қолданбайды.

long long үшін gcd

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 өзара жай сандар.

Кеңейтілген Евклид алгоритмі

Extended Euclid мынадай x және y сандарын табады:

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

Бұл керек болады:

сызықтық диофант теңдеулерінде
модуль бойынша inverse табуда
number theory задачаларында

Кеңейтілген Евклид коды

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

Extended Euclid мысалы

Берілсін:

a = 30
b = 18

НОД:

gcd(30, 18) = 6

Мысалы:

x = -1
y = 2

Тексеру:

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

Extended Euclid толық коды

#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 қолданылатын типтік задачалар

екі санның НОД-ын табу
екі санның НОК-ын табу
массивтің НОД-ын табу
сандар өзара жай ма тексеру
дробьты қысқарту
period табу
ax + by = c түріндегі теңдеуді шешу

Дробьты қысқарту

Дробь берілсін:

a / b

Оны қысқарту үшін числитель мен знаменательді НОД-қа бөлеміз.

long long d = gcd(a, b);

a /= d;
b /= d;

Мысал:

12 / 18 = 2 / 3

Типтік қателер

НОД — кіші сан деп ойлау
НОД пен НОК-ты шатастыру
Евклид орнына баяу перебор жазу
gcd(a, 0) = a екенін ұмыту
a * b / gcd жазып overflow алу
int қолдану, ал long long керек болуы
теріс сандар үшін abs алмау

Асимптотика

Метод	Уақыт	Память
Жай НОД	O(min(a, b))	O(1)
Евклид алгоритмі	O(log min(a, b))	O(1)
Extended Euclid	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);
}