Условие
Наименьшим общим кратным ($НОК$) множества натуральных чисел называется такое наименьшее натуральное число, которое делится на каждое число в этом множестве. Например, $НОК$ чисел $5$, $7$ и $15$ равно $105$.
Вам необходимо найти $НОК$ $m$ заданных чисел.
Входные данные
Первая строка содержит количество тестов. Каждый тест состоит из одной строки и содержит числа $m$ $n_1$ $n_2$ $n_3$ $\ldots$ $n_m$, где $m$($1 \leqslant m \leqslant 100$) — количество заданных чисел, $n_1$ $\ldots$ $n_m$ — сами числа. Все числа натуральные и лежат в границах $32$-битового целого.
Выходные данные
Для каждого теста в отдельной строке вывести соответствующее значение $НОК$. Все выводимые числа лежат в границах $32$-битового целого.
Тесты
| № | ввод | вывод |
|---|---|---|
| 1 | 2 3 5 7 15 6 4 10296 936 1287 792 1 |
105 10296 |
| 2 | 3 1 36 5 2 2 2 2 2 5 987 1597 2584 4181 6765 10946 17711 |
36 2 38400890173772280 |
| 3 | 0 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #include <algorithm> using namespace std; int main() { int n, m; cin >>n; for(int i=0; i<n; i++) { cin >>m; int temp, ans; cin >>ans; for(int j=1; j<m; j++) { cin >>temp; ans = ans/__gcd(ans, temp)*temp; } cout <<ans <<endl; } } |
Код с алгоритмом Евклида
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <algorithm> using namespace std; int gcd(int a, int b) { while(a and b) { if(a>b) a %= b; else b %= a; } return a+b; } int main() { int n, m; cin >>n; for(int i=0; i<n; i++) { cin >>m; int temp, ans; cin >>ans; for(int j=1; j<m; j++) { cin >>temp; ans = ans/gcd(ans, temp)*temp; } cout <<ans <<endl; } } |
Решение
$\DeclareMathOperator{\lcm}{lcm}$
$НОК$ ($\lcm$) проще всего считается по формуле $\operatorname {lcm}(a,b)={\frac {|a\cdot b|}{\operatorname {gcd}(a,b)}}$, где $\gcd$ — $НОД$. Для $\lcm$ от более чем двух чисел справедлива следующая формула: $\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{n})=\operatorname {lcm}(\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{{n-1}}),a_{n})$, из которой видно, что подсчёт $\lcm$ от $n$ чисел сводится к вычислению $n-1$-ого $\lcm$ от очередного числа и предыдущего результата вычислений.
$НОД$ ($\gcd$) в коде считается при помощи стандартной функции __gcd(a, b) из стандартной библиотеки algorithm в первом варианте кода или по алгоритму Евклида во втором.
— Пожалуйста, сделайте знаки меньше либо равно такими, как в Ваших учебниках.
— Функции НОД и НОК в формулах то наклонные, то прямые. Используйте везде прямое начертание для математических функций.
— Зачем эта чехарда в строка 11 и 12? Что мешает сразу прочесть в нужную переменную?
— Зачем умножение перед делением брать в скобки? Чтобы получить число побольше? Я бы еще понял, если бы вы деление брали в скобки. Тогда можно везде int использовать.
— Ну, и ваша функция вычисления НОД мне не очень нравится. Зачем каждый раз проверять кто больше? После первого вычисления остатка от деления уже ясно, кто больше. Можно было, например так написать:
Хотя, не сильно лучше вышло. Я всегда так пишу:
Короче получается. Но, давайте оставим Ваш вариант. Не такой уж он и плохой.