Задача
Найдите $НОК$ (наименьшее общее кратное) двух натуральных чисел.
Входные данные
Два натуральных числа $a$ и $b$ $(a, b < 2 \cdot 10^9)$.
Выходные данные
Вывести $НОК$ чисел $a$ и $b$.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 42 24 | 168 |
| 2 | 32 14 | 224 |
| 3 | 101 45 | 4545 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> using namespace std; long int GCD(int num1, int num2) { if(num1 == num2) return num1; while(num1 && num2) { if(num1 > num2) num1 %= num2; else num2 %= num1; } return num1+num2; } int main() { long int num1, num2, gcd; cin >> num1 >> num2; gcd = GCD(num1, num2); cout << num1*num2/gcd; return 0; } |
Решение
Пусть есть два числа $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$. Если есть остаток, то большее число заменяется на остаток от деления и все действия повторяются.
После завершения цикла в одной переменной содержится ноль, а другая равна $НОД$, но поскольку неизвестно, которая из переменных равна $НОД$, то возвращается их сумма.
Ссылки
- Код на ideone
- Задача на e-olymp
- Засчитанное решение на e-olymp
Евгения, я бы посоветовал Вам представить формулу для нахождения $НОК$ в описании решения в более удобном для восприятия виде: $НОК(n_1, n_2)={{n_1\cdot n_2}\over{НОД(n_1, n_2)}}$
Поддерживаю.
И учтите, что если вы пишите формулу, то разумно писать $n_1.$ Если вы цитируете программу, то нужно писать та num1. Вы же отличаете одно от другого?
— Конечно, можно заменять деление многократным вычитанием, но мысль остального человечества пошла строго в противоположную сторону 🙂 Почитайте что-нибуь по алгоритму Эвклида.
— Что за странный выбор категорий? Как вы себе представляете линейные вычисления, которые ветвятся и ходят по циклу? Я думал это может только Пелевин.
Исправила. Изначально решила вычитанием, потому что на сайте недавно было опубликовано решение похожей задачи делением. Поэтому использовала другой способ.
Категорию «линейные вычисления», по всей видимости, выбрала случайно и не заметила.
— А почему просто не вызвать стандартную функцию?
— По категориям. Вы же решали задачи тематических контестов, вы видите десятки задач в категориях, вы видите описание категории! Эти категории идут по добавлению функциональности. В задачах на условный оператор нельзя использовать циклы. В линейных нельзя использовать ветвление и циклы.