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

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

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

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

  • Вычислять НОК через НОД
  • Избегать переполнения, деля перед умножением
  • Переиспользовать одну функцию внутри другой

Условие

Верните наименьшее общее кратное a и b — наименьшее положительное число, на которое делятся оба числа. lcm(a, b) = a / gcd(a, b) × b.

Реализуйте функцию lcm(a, b).

Ввод

a: Первое положительное число. b: Второе положительное число.

Вывод

Верните lcm(a, b).

Ограничения

1 ≤ a, b ≤ 1 000 000 000

Примеры

Пример 1
Ввод:
a = 4
b = 6

Ожидаемый вывод:
expected = 12
Ввод:
long long a = 4;
long long b = 6;

Ожидаемый вывод:
long long expected = 12;
Ввод:
long a = 4;
long b = 6;

Ожидаемый вывод:
long expected = 12;

Пояснение

Кратные 4: 4, 8, 12…; кратные 6: 6, 12…; первое общее — 12.

Пример 2
Ввод:
a = 7
b = 7

Ожидаемый вывод:
expected = 7
Ввод:
long long a = 7;
long long b = 7;

Ожидаемый вывод:
long long expected = 7;
Ввод:
long a = 7;
long b = 7;

Ожидаемый вывод:
long expected = 7;

Пояснение

НОК числа с самим собой — это само число: 7.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Используйте связь между gcd и lcm вместо поиска кратных.

Подсказка 2

Сначала найдите gcd, затем аккуратно объедините два числа.

Подсказка 3

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

Ожидаемая сложность

время O(log min(a, b)), доп. память O(1)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

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

# Участник Язык Время Память Оценка ИИ Решение
1 HJhettory Jurash Python 1,017 ms - 4/5 Посмотреть код

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

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

Внимание, спойлер: ниже 1 полное решение Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.