e-olymp 1602. НОК двух натуральных чисел

Задача

Найдите $НОК$ (наименьшее общее кратное) двух натуральных чисел.

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

Два натуральных числа $a$ и $b$ $(a, b < 2 \cdot 10^9)$.

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

Вывести $НОК$ чисел $a$ и $b$.

Тесты

Входные данные Выходные данные
1 42 24 168
2 32 14 224
3 101 45 4545

Код

Решение

Пусть есть два числа $n_1$ и $n_2$. $НОК$($n_1$, $n_2$) можно вычислить по формуле $НОК(n_1, n_2)={{n_1\cdot n_2}\over{НОД(n_1, n_2)}}$. Тогда задача сводится к нахождению $НОД$ двух чисел, который вычисляется алгоритмом Евклида:
$1$. Большее число делится на меньшее.
$2$. Если остаток от деления равен нулю, то меньшее число и есть $НОД$.
$3$. Если есть остаток, то большее число заменяется на остаток от деления и все действия повторяются.
После завершения цикла в одной переменной содержится ноль, а другая равна $НОД$, но поскольку неизвестно, которая из переменных равна $НОД$, то возвращается их сумма.

Ссылки

5 thoughts on “e-olymp 1602. НОК двух натуральных чисел

  1. Евгения, я бы посоветовал Вам представить формулу для нахождения $НОК$ в описании решения в более удобном для восприятия виде: $НОК(n_1, n_2)={{n_1\cdot n_2}\over{НОД(n_1, n_2)}}$

    • Поддерживаю.
      И учтите, что если вы пишите формулу, то разумно писать $n_1.$ Если вы цитируете программу, то нужно писать та num1. Вы же отличаете одно от другого?

  2. — Конечно, можно заменять деление многократным вычитанием, но мысль остального человечества пошла строго в противоположную сторону 🙂 Почитайте что-нибуь по алгоритму Эвклида.
    — Что за странный выбор категорий? Как вы себе представляете линейные вычисления, которые ветвятся и ходят по циклу? Я думал это может только Пелевин.

    • Исправила. Изначально решила вычитанием, потому что на сайте недавно было опубликовано решение похожей задачи делением. Поэтому использовала другой способ.
      Категорию «линейные вычисления», по всей видимости, выбрала случайно и не заметила.

    • — А почему просто не вызвать стандартную функцию?
      — По категориям. Вы же решали задачи тематических контестов, вы видите десятки задач в категориях, вы видите описание категории! Эти категории идут по добавлению функциональности. В задачах на условный оператор нельзя использовать циклы. В линейных нельзя использовать ветвление и циклы.

Добавить комментарий