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

Материал из Algocode wiki
Версия от 14:40, 10 октября 2019; Romanchenko (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

НОК и НОД

Теория

Определение:
Наибольший общий делитель(GCD, НОД) набора чисел $a_n$ —это максимальное число $x$ такое, что на него делятся все $a_i$.

Определение:
Наименьшее общее кратное(LCM, НОК) набора чисел $a_n$ —это минимальное число $x$ такое, что оно делит все $a_i$.

Примеры:

  1. $НОД(18, 30) = 6$
  2. $НОД(60, 180, 315) = 15$
  3. $НОД(1, N) = 1$
  4. $НОК(12, 30) = 6$
  5. $НОК(1, 2, 3, 4) = 12$
  6. $НОК(1, N) = N$

Для краткости обыкновенно используют следующие обозначения: $$(a,b) = НОД(a, b) \ \ \ [a, b] = НОК(a, b)$$

Утверждение:
$[a,b] = \frac{ab}{(a,b)}$

Доказательство:
рассмотрим мультимножество простых делителей чисел $a$ и $b$. То есть если число делится на $5^2$, то пятерка войдет дважды в это множество. Осталось понять, что НОД - пересечение этих двух мультимножеств, а НОК - объединение. Чтобы получить объединение мы берем элементы из обоих мультимножеств (умножаем $a$ на $b$), а потом убираем из этого множества пересечение исходных (делим на НОД)

Задача-пример 1

Есть $n$ шестеренок, каждая $i$-ая зацеплена с $(i-1)$-ой. $i$-ая шестеренка имеет $a_i$ зубчиков. Сколько раз нужно повернуть полностью первую шестеренку, чтобы все остальные шестеренки тоже вернулись на изначальное место?

Решение: Когда одна шестеренка крутится на 1 зубчик, все остальные тоже крутятся на один зубчик. Нужно найти минимальное такое число зубчиков $x$, что при повороте на него все шестеренки вернутся в изначальное положение, то есть $x$ делится на все $a_i$, то есть это $[a_1, a_2, \ldots, a_n]$. Ответом будет $\frac{x}{a_1}$.

Задача-пример 2

Город — это прямоугольник $n$ на $m$, разделенный на квадраты единичного размера. Вертолет летит из нижнего левого угла в верхний правый по прямой. Вертолет будит людей в квартале, когда он пролетает строго над его внутренностью (границы не считаются). Сколько кварталов разбудит вертолёт?

Решение: Вертолет пересечет по вертикали $(m-1)$ границу. С этим ничего не поделать — каждое пересечение считается как новое посещение какого-то квартала. По горизонтали то же самое — $(n-1)$ переход в новую ячейку будет сделан.

Однако еще есть случай, когда он пересекает одновременно обе границы (то есть пролетает над каким-нибудь углом) — ровно тот случай, когда нового посещения квартала не происходит. Сколько таких будет? Ровно столько, сколько есть целых решений уравнения: $$\dfrac{n}{m} = \dfrac{x}{y}$$ Мы как бы составили уравнение движения вертолёта и ищем, в скольки целых точках оно выполняется.

Пусть $t = (n, m)$, тогда $n = at, m = bt \ \Rightarrow \ \dfrac{n}{m} = \dfrac{a}{b} = \dfrac{x}{y}$.

Любая дробь с натуральными числителем и знаменателем имеет ровно одно представление в виде несократимой дроби, так что $x$ должно делиться на $a$, а $y$ должно делиться на $b$. А значит, как ответ подходят пары: $$(a, b), (2a, 2b), (3a, 3b), \cdots, ((t-1)a, (t-1)b)$$ Таких ответов ровно $t - 1 = (n, m) - 1$ Значит, итоговый ответ: $(n-1) + (m-1) - (t-1)$.

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

Легко проверить, что $(a, b) = (a - b, b), \ a \ge b$. Отсюда будет следовать, что $(a, b) = (a \mod b, b)$, где $a \mod b$ означает взятие остатка от деления $a$ на $b$. Это верно, так как взятие остатка - это то же самое, что многократное вычитание из $a$ $b$, пока результат не станет меньше $b$.

Алгоритм Евклида заключается в том, чтобы подаваемые на вход числа уменьшались с помощью такого преобразования (взятия остатка), пока одно из них не станет равно нулю. Заметим, что $(0, x) = x, \ \ x \neq 0$. В данном случае ответ очевиден. Алгоритм будет выглядеть так:

1 int gcd(int a, int b) {
2     while (b != 0) {
3         int c = a % b;
4         a = b;
5         b = c;
6     }
7     return a;
8 }

>

См. также



Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko