Как найти нок с помощью алгоритма евклида

Наибольший общий делитель

Как несложно догадаться, наибольший общий делитель (англ. greatest
common divisor) двух целых чисел — наибольшее число, на которое делится
каждое из них. Например:

[gcd(15, 20) = 5]

[gcd(12, 30) = 6]

Сразу заметим важное свойство:

[gcd(a, b) = gcd(b, a)]

НОД играет большую роль как в математике, так и в программировании, и часто
встречается в задачах на различные темы.

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

Алгоритм Евклида — один из первых алгоритмов в истории, использовался
ещё в Древней Греции, и дошёл до наших дней. В изначальном виде он назывался
“взаимным вычитанием”, так как заключался в поочерёдном вычитании меньшего
числа из большего, пока одно из них не станет равным 0. Сегодня чаще всего
вместо вычитания используется взятие остатка от деления, но суть алгоритма
сохранилась.

Алгоритм заключается в построении ряда чисел следующего вида ((a > b)):

[a, b, r_1, r_2, ldots, r_n]

Где каждое последующее число является остатком от деления предпредыдущего
на предыдущее:

[r_1 = a bmod b \
r_2 = b bmod r_1 \
ldots \
r_n = r_{n — 2} bmod r_{n — 1}]

Ряд заканчивается, когда остаток от деления предпоследнего числа на
последнее становится равным 0:

[r_{n — 1} bmod r_n = 0]

В таком случае утверждается, что:

[gcd(a, b) = r_n]

Для доказательства этого утверждения сначала докажем следующее:
наборы общих делителей пары ((a, b)) и пары ((b, r_1)) полностью совпадают.
Рассмотрим произвольный (не обязательно наибольший) общий делитель (a) и (b):

(t) — общий делитель (a) и (b).

(r_1 = a bmod b), или (a = bq + r_1).

Докажем, что (t) также является общим делителем (b) и (r_1).

(b) делится на (t) по определению.

(r_1 = a — bq = t * ({a over t} — {b over t} * q)), где ({a over t}) и ({b over t}) целые по определению.

Значит, (r_1) также делится на (t), что и требовалось доказать.

Из того, что все общие делители пар ((a, b)) и ((b, r_1)) совпадают,
в частности следует, что (gcd(a, b) = gcd(b, r_1)).

Далее по индукции можно доказать следующее:

[gcd(a, b) = gcd(b, r_1) = gcd(r_1, r_2) = ldots = gcd(r_{n — 1}, r_n) = gcd(r_n, 0)]

(Нуль в последнем выражении появился из условия (r_{n — 1} bmod r_n = 0)).

Нуль делится на все числа, отличные от нуля, поэтому справедливо следующее
свойство:

[gcd(x, 0) = x, для любого x in mathbb{N}.]

Следовательно,

[gcd(a, b) = r_n,]

что и требовалось доказать.

Варианты реализации алгоритма Евклида на C++

Существует несколько вариантов реализации алгоритма Евклида, как итеративных
так и рекурсивных. Классическая итеративная реализация (работающая быстрее всех
рекурсивных) выглядит так:

1
2
3
4
5
6
7
8
9
10
11
12



int gcd(int a, int b) {
    if (a < b) {
        swap(a, b);
    }

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

    return a;
}






Рекурсивно это же можно реализовать так:
1
2
3
4
5
6
7
8
9
10
11



int gcd(int a, int b) {
    if (a < b) {
        swap(a, b);
    }

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






Преимущество рекурсивной реализации заключается в возможности записать её в

очень кратком виде (предполагающим, что (a > b)):
1
2
3



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









  


                       
  




На практике разница во времени работы итеративного и рекурсивного вариантов

не столь значительна, так что вы можете использовать любой из них.
Время работы алгоритма Евклида
Согласно некоторым исследованиям, время работы алгоритма Евклида тесно

связано с числами Фибоначчи. Это выражается, в частности, в том, что два

последовательных числа Фибоначчи — наихудшие входные данные для алгоритма

Евклида. При (a = F_n, b = F_{n — 1}), алгоритм Евклида совершит ровно

(n — 2) итерации. Отсюда можно выразить асимптотическую сложность алгоритма:

последовательность Фибоначчи возрастает с экспоненциальной скоростью, поэтому

алгоритм Евклида работает за (O(log min(a, b))).
Наименьшее общее кратное
С понятием НОД связано также понятия наименьшего общего кратного (англ.

least common multiple). Наименьшее общее кратное двух натуральных чисел —

наименьшее натуральное число, которое делится на каждое из них. Оно обозначается

следующим образом:
[lcm(a, b)]
и связано с НОД формулой:
[lcm(a, b) = {a * b over gcd(a, b)}]
Реализация на C++:
1
2
3
4
5



int lcm(int a, int b) {
    return a / gcd(a, b) * b;   //используя форму a * b / gcd(a, b),
                                //можно получить переполнение на этапе a * b,
                                //поэтому следует выполнять деление до умножения
}






Взаимнопростые числа
Числа (a) и (b) называются взаимнопростыми тогда и только тогда, когда они

не имеют общих делителей отличных от (1). То есть в их отношении должно

выполняться условие (gcd(a, b) = 1).
НОД и НОК для произвольного количества чисел
Обе функции легко обобщаются для произвольного числа аргументов

последовательным применением:
[gcd(a, b, c, d) = gcd(gcd(gcd(a, b), c), d)]
[lcm(a, b, c, d) = lcm(lcm(lcm(a, b), c), d)]