Least Common Multiple
Даны два положительных целых числа a и b. Верните их наименьшее общее кратное: наименьшее положительное целое число, которое делится и на a, и на b без остатка.
Функция
- 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не существует.
Дополнительный вопрос
Сможешь найти НОД, совсем не используя деление или остаток от деления, а только вычитание и деление пополам?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Ответ является кратным большему числу. Нужно ли проверять каждое число между ними или только кратные большему числу?
Наибольший общий делитель и наименьшее общее кратное связаны между собой:
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, пока оба числа не будут делить его без остатка; ты проверяешь кандидатов в порядке возрастания, поэтому первое найденное число — наименьшее. Для 4 и 6 ты проверяешь числа от 6 до 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, 2 × big, 3 × big и остановись на первом числе, которое делится на меньшее число. Для 4 и 6 ты проверяешь 6, затем 12.
Поскольку 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 × lcm = a × b. Для 4 = 2² и 6 = 2 × 3 НОД равен 2, а НОК — 2² × 3 = 12.
Алгоритм Евклида находит НОД за 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 происходит паника), хотя НОК помещается. - Выполнять деление с плавающей точкой. Результат может получиться таким:
2.146654199E9, или в нём могут потеряться последние цифры; используйте только целые числа. - Запускать цикл Евклида непосредственно на
aиb. После этого в них будут храниться НОД и0, поэтому работайте с копиями. - Предполагать, что ответ — это
a × b. Это верно, только если у чисел нет общих множителей:lcm(4, 6)равно12, а не24.
Частые вопросы3
Какова формула для НОК двух чисел?
lcm(a, b) = a × b / gcd(a, b), вычисляется как a / gcd(a, b) × b, чтобы промежуточное значение не превышало ответ. Для 4 и 6 НОД равен 2, а 4 / 2 × 6 = 12.
Какова временная сложность вычисления НОК?
При использовании формулы НОД временная сложность составляет 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-битные целые числа.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def lcm(a, b):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргументы
a = 4 b = 6
Ожидаемый вывод
12