Все задачи
Легко Решено: 0 Процент решений: 0%

Наименьшее общее кратное диапазона

Найдите наименьшее положительное число, которое делится на каждое целое число из диапазона.

Чему вы научитесь

  • Вычислять lcm(a, b) через gcd(a, b)
  • Сворачивать операцию по диапазону чисел
  • Не допускать переполнения промежуточных значений

Условие

Пекарня раскладывает печенье по коробкам всех размеров от lo до hi. Нужна такая партия, которую можно без остатка разложить по коробкам любого из этих размеров. Ответ - наименьшее положительное число, которое делится на все целые числа от lo до hi, то есть их наименьшее общее кратное.

Реализуйте smallest_multiple(lo, hi).

Входные данные

lo: наименьший размер коробки.

hi: наибольший размер коробки.

Выходные данные

Верните наименьшее положительное целое число, которое делится без остатка на каждое из чисел lo, lo + 1, ..., hi.

Ограничения

1 ≤ lo ≤ hi ≤ 40 (ответ помещается в знаковое 64-битное целое)

Примеры

Пример 1
Ввод:
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.

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.