GCD, LCM и алгоритм Евклида
Быстро и правильно вычисляйте делители
«GCD, LCM и алгоритм Евклида» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Почему важны делители
Многие задачи соревнований зависят от общих делителей двух чисел. Самый полезный инструмент здесь — GCD, наибольший общий делитель. 🔢
Что означает GCD
GCD двух целых чисел — это наибольшее число, на которое оба числа делятся без остатка. Для 12 и 18 это 6, поскольку 6 делит оба числа нацело.
Медленный способ
Можно проверять все числа, начиная с меньшего и двигаясь вниз, пока не найдётся число, которое делит оба числа. Это работает, но слишком медленно для больших входных данных.
Идея Евклида
Алгоритм Евклида — быстрый способ решения задачи. Его ключевая идея такова: GCD чисел a и b равен GCD числа b и остатка от деления a на b.
Рекуррентный шаг
Повторяйте шаг с перестановкой и взятием остатка, пока остаток не станет равен нулю. Последнее оставшееся ненулевое значение — это ваш результат, сам GCD.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aНапишите код самостоятельно
Короткий цикл заменяет пару чисел, пока b не станет равным нулю. Он выполняется примерно за логарифмическое число шагов — очень быстро даже для огромных чисел.
def gcd(a, b):
while b:
a, b = b, a % b
return aИспользуйте стандартную библиотеку
Обычно нет необходимости писать этот алгоритм вручную. Python предоставляет math.gcd: эта функция корректна, быстра и сама обрабатывает нулевые аргументы.
from math import gcd
print(gcd(12, 18))От GCD к LCM
LCM, наименьшее общее кратное, — это наименьшее число, на которое делятся оба значения. Оно напрямую связано с вычисленным вами GCD.
Формула LCM
Перемножьте два числа, а затем разделите результат на их GCD. При очень больших произведениях всегда сначала выполняйте деление, чтобы избежать переполнения.
def lcm(a, b):
return a // gcd(a, b) * bGCD целого списка
Чтобы последовательно вычислить GCD для многих чисел, применяйте его попарно. Функция свёртки в Python применяет math.gcd слева направо ко всему списку.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Обработайте случай с нулём
По определению gcd(a, 0) равно a, а gcd(0, 0) равно 0. Знание этого граничного случая не позволяет циклам работать неправильно на пустых входных данных.
Быстрая проверка
Пора проверить основной шаг алгоритма Евклида.
Итоги
Теперь вы умеете вычислять GCD с помощью алгоритма Евклида за логарифмическое число шагов, получать из него LCM и последовательно вычислять оба значения для списка. ✅
Часто задаваемые вопросы
Урок «GCD, LCM и алгоритм Евклида» бесплатный?
Да — полный текст урока «GCD, LCM и алгоритм Евклида» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «GCD, LCM и алгоритм Евклида»?
Быстро и правильно вычисляйте делители Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «GCD, LCM и алгоритм Евклида»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- GCD, LCM и алгоритм Евклида
- Проверка простоты до sqrt(n)
- Решето Эратосфена
- Разложение на простые множители и делители