Пекарня раскладывает печенье по коробкам всех размеров от lo до hi. Нужна такая партия, которую можно без остатка разложить по коробкам любого из этих размеров. Ответ - наименьшее положительное число, которое делится на все целые числа от lo до hi, то есть их наименьшее общее кратное.
Реализуйте smallest_multiple(lo, hi).
Входные данные
lo: наименьший размер коробки.
hi: наибольший размер коробки.
Выходные данные
Верните наименьшее положительное целое число, которое делится без остатка на каждое из чисел lo, lo + 1, ..., hi.
Ограничения
1 ≤ lo ≤ hi ≤ 40 (ответ помещается в знаковое 64-битное целое)
Примеры
Ввод:
lo = 1
hi = 6
Ожидаемый вывод:
expected = 60
Ввод:
long long lo = 1;
long long hi = 6;
Ожидаемый вывод:
long long expected = 60;
Ввод:
long lo = 1;
long hi = 6;
Ожидаемый вывод:
long expected = 60;
Пояснение
60 делится на 1, 2, 3, 4, 5 и 6, и меньшего положительного числа с таким свойством нет, поэтому ответ 60.
Ввод:
lo = 4
hi = 6
Ожидаемый вывод:
expected = 60
Ввод:
long long lo = 4;
long long hi = 6;
Ожидаемый вывод:
long long expected = 60;
Ввод:
long lo = 4;
long hi = 6;
Ожидаемый вывод:
long expected = 60;
Пояснение
НОК(4, 5) = 20 и НОК(20, 6) = 60, так что ответ снова 60: маленькие размеры ничего не добавили.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
НОК целого диапазона можно строить, добавляя по одному числу.
Подсказка 2
НОК(a, b) = a / НОД(a, b) × b.
Подсказка 3
Сначала делите, потом умножайте, тогда промежуточное значение никогда не превысит ответ.
Ожидаемая сложность
время O(n log M), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.