Least Common Multiple
Даны два положительных целых числа a и b. Верните их наименьшее общее кратное: наименьшее положительное целое число, на которое и a, и b делятся без остатка.
Например, кратные 6 — это 6, 12, 18, 24 и так далее, кратные 8 — это 8, 16, 24 и так далее, а первое число в обоих списках — 24.
Функция
- ainteger
- первое положительное целое число
- binteger
- второе положительное целое число
- Возвращаетinteger
- наименьшее положительное целое число, кратное и a, и b
Ограничения
1 ≤ a ≤ 1061 ≤ b ≤ 106- Ответ помещается в знаковое 32-битное целое число:
lcm(a, b) ≤ 231-1. Произведениеa × bможет не помещаться.
Примеры
- Ввод
- a = 4b = 6
- Вывод
- 12
- Пояснение
- Кратные
6начинаются с 6, 12, 18; кратные4начинаются с 4, 8, 12. Первое число в обоих списках —12.
- Ввод
- a = 7b = 3
- Вывод
- 21
- Пояснение
7и3не имеют общих делителей, кроме1, поэтому их наименьшее общее кратное равно их произведению —21.
- Ввод
- a = 15b = 45
- Вывод
- 45
- Пояснение
15делит45без остатка, поэтому45уже является общим кратным, и меньшего кратного45не существует.
+15 скрытых тестов при отправке
Дополнительный вопрос
Можешь найти НОД, совсем не используя деление или остаток, а только вычитание и деление пополам?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Ответ является кратным большему числу. Нужно ли проверять каждое число между ними или только числа, кратные большему?
Наибольший общий делитель и наименьшее общее кратное связаны:
gcd(a, b) × lcm(a, b) = a × b. Алгоритм Евклида находит НОД за несколько десятков шагов.Вычисли НОД, затем верни
a / gcd × b. Сначала раздели: произведениеa × bможет переполнить 32-битное целое число, даже если ответ помещается.
Решение
Наименьшее общее кратное и наибольший общий делитель — две стороны одного факта: gcd(a, b) × lcm(a, b) = a × b. Поэтому быстрый ответ — a × b / gcd(a, b), но есть один нюанс. Произведение может достигать 10^12, что приводит к переполнению 32-битного целого числа, даже если результат помещается в него, поэтому сначала нужно разделить на НОД, а затем умножить.
Считай вверх, начиная с большего числа
Верно, но не успевает на самых больших тестах
Идея
Ответ кратен обоим числам, поэтому он не меньше большего из них. Начни с кандидата m, равного max(a, b), и прибавляй 1, пока и a, и b не будут делить его. Ты проверяешь кандидатов в порядке возрастания, поэтому первый подходящий кандидат и есть наименьший.
Для 4 и 6 ты проверяешь 6, 7, 8, 9, 10 и 11 — они не подходят, — и останавливаешься на 12. Цикл всегда завершается, потому что a × b — общее кратное.
Количество попыток примерно равно величине ответа. Для 46337 и 46327, двух простых чисел, ответ равен 2146654199, поэтому цикл выполняется более двух миллиардов раз. Это слишком медленно.
Алгоритм
- Присвой
mбольшее из значенийaиb. - Пока
m % aилиm % bне равно0, увеличивайmна 1. - Верни
m.
def lcm(a, b):
m = max(a, b)
while m % a != 0 or m % b != 0:
m += 1
return mПеребирайте кратные большего числа
Идея
Большинство кандидатов при подсчёте не подходят: ответ должен быть кратен большему числу, назовём его big. Поэтому сразу переходи от одного кратного big к следующему: big, 2 × big, 3 × big — и остановись на первом числе, которое делится на меньшее число.
Для 4 и 6 ты проверяешь 6 (4 на него не делится), а затем 12 (делится). Ответ равен k × big для некоторого k, причём k не больше меньшего числа, поскольку small × big всегда является общим кратным. Значит, цикл выполняется не более min(a, b) раз, что здесь никогда не превышает миллиона.
Здесь это достаточно быстро, но время выполнения всё же растёт вместе с входными данными. Для чисел до 10^18 такой подход уже не подошёл бы.
Алгоритм
- Пусть
big— большее число, аsmall— меньшее. - Установи
m = big. - Пока
m % smallне равно0, прибавляйbigкm. - Верни
m.
def lcm(a, b):
big, small = max(a, b), min(a, b)
m = big
while m % small != 0:
m += big
return mРазделите на НОД, затем умножьте
Идея
Разложите оба числа на простые множители. НОД берёт каждый простой множитель в меньшей из двух его степеней, НОК — в большей, и вместе они используют каждый множитель числа a и числа b ровно один раз. Получаем gcd(a, b) × lcm(a, b) = a × b, поэтому lcm(a, b) = a × b / gcd(a, b). Для 4 = 2² и 6 = 2 × 3 НОД равен 2, а НОК равен 2² × 3 = 12.
Найдите НОД с помощью алгоритма Евклида: заменяйте (x, y) на (y, x % y), пока y не станет равным 0. Это займёт O(log(min(a, b))) шагов.
Затем вычислите a / gcd × b именно в таком порядке. НОД делит a без остатка, поэтому при делении ничего не теряется, а результат никогда не превышает ответ. Если вместо этого записать a × b / gcd, произойдёт переполнение 32-битного целого числа при a = b = 10^6: произведение равно 10^12, тогда как ответ составляет всего 10^6.
Алгоритм
- Скопируй
aиbвxиy. - Пока
yне равно0, заменяй(x, y)на(y, x % y). Теперьx— это НОД. - Раздели
aнаx. - Умножь результат на
bи верни его.
def lcm(a, b):
x, y = a, b
while y != 0:
x, y = y, x % y
# x is gcd(a, b). Divide before multiplying.
return a // x * b
Ловушки и крайние случаи
Формула состоит из одной строки, а ошибки связаны с порядком арифметических операций.
- Сначала вычисляется
a × b. В Java, C, C++, C# и Rust произведение двух чисел, близких к10^6, переполняет 32-битное целое число, поэтому ответ получается неправильным или отрицательным (а сборка Rust для отладки вместо этого вызывает панику), хотя истинное НОК помещается в диапазон. - Деление
a × bна НОД с использованием чисел с плавающей точкой. Результат может оказаться равным2.146654199E9или потерять последние цифры; используйте только целые числа. - Запуск цикла Евклида непосредственно для
aиb, а затем использование их в формуле. После цикла в них хранятся НОД и0, поэтому работайте с копиями. - Предположение, что ответ равен
a × b. Это верно, только если у двух чисел нет общих множителей:lcm(4, 6)равно12, а не24.
Частые вопросы4
Какова формула НОК двух чисел?
lcm(a, b) = a × b / gcd(a, b), вычисляемое как a / gcd(a, b) × b, чтобы промежуточное значение никогда не превышало ответ. Для 4 и 6 НОД равен 2, а 4 / 2 × 6 = 12.
Почему gcd(a, b) × lcm(a, b) равно a × b?
Для каждого простого числа НОД использует меньшую из его степеней в a и b, а НОК — большую. Меньшая степень плюс большая — это сумма обеих степеней, которая в точности равна степени этого простого числа в a × b. Для каждого простого числа это верно, поэтому два произведения равны.
Какова временная сложность вычисления НОК?
При использовании формулы НОД сложность составляет O(log(min(a, b))) — стоимость алгоритма Евклида — плюс одно деление и одно умножение. Для этого требуется O(1) дополнительной памяти. Поиск среди кратных работает гораздо медленнее: O(min(a, b)), если увеличивать значение на большее число, и O(lcm(a, b)), если считать по единице.
Как найти НОК более чем двух чисел?
Сворачивайте список: lcm(a, b, c) = lcm(lcm(a, b), c). Для [4, 6, 10]: lcm(4, 6) = 12 и lcm(12, 10) = 60. Текущее значение быстро растёт, поэтому следите за переполнением и используйте 64-битные целые числа, если список длинный.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def lcm(a, b):
# Напишите код здесьСлучай 1
Случай 2
Случай 3
Ввод
a = 4 b = 6
Ожидается
12