Алгоритм Евклида: различия между версиями
Строка 50: | Строка 50: | ||
==Алгоритм Евклида== | ==Алгоритм Евклида== | ||
− | Легко проверить, что $(a, b) = (a - b, b), \ a \ge b$. Отсюда будет следовать, что $(a, b) = (a | + | Легко проверить, что $(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$. В данном случае ответ очевиден. | Алгоритм Евклида заключается в том, чтобы подаваемые на вход числа уменьшались с помощью такого преобразования (взятия остатка), пока одно из них не станет равно нулю. Заметим, что $(0, x) = x, \ \ x \neq 0$. В данном случае ответ очевиден. |
Текущая версия на 14:40, 10 октября 2019
Содержание
НОК и НОД
Теория
Определение:
Наибольший общий делитель(GCD, НОД) набора чисел $a_n$ —это максимальное число $x$ такое, что на него делятся все $a_i$.
Определение:
Наименьшее общее кратное(LCM, НОК) набора чисел $a_n$ —это минимальное число $x$ такое, что оно делит все $a_i$.
Примеры:
- $НОД(18, 30) = 6$
- $НОД(60, 180, 315) = 15$
- $НОД(1, N) = 1$
- $НОК(12, 30) = 6$
- $НОК(1, 2, 3, 4) = 12$
- $НОК(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