e-olymp 1243. Наименьшее общее кратное

20/12/2020 by Максим Ливитчук

Условие

Наименьшим общим кратным ($НОК$) множества натуральных чисел называется такое наименьшее натуральное число, которое делится на каждое число в этом множестве. Например, $НОК$ чисел $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

Код

#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;
    }
}

#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;

}

Код с алгоритмом Евклида

#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;
    }
}

#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 в первом варианте кода или по алгоритму Евклида во втором.

Ссылки

Related Images:

e-olymp 571. НОД

27/12/2017 by Яна Колчинская

Задача

Найти НОД (наибольший общий делитель ) $n$ чисел.

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

Первая строка содержит количество чисел [latex]n \left(1 < n < 101\right)[/latex]. Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает [latex]30000[/latex].

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

НОД заданных чисел.

Тесты

#	Входные данные	Выходные данные
1	3 5 7 2	1
2	2 45 10	5
3	4 27 90 15 9	3
4	2 40 64	8
5	3 8 8 8	8

Код

#include <iostream>
using namespace std;
int gcd (int a, int b) {
    while (a!=0 && b!=0) {
        if (a>b) {
            a=a%b;
        }
        else b=b%a;
    }
    return a+b;
}

int main () {
    int t, a, b;
    cin>>t>>b;
    for (int i=2; i<=t; ++i) {
        cin>>a;
        b=gcd (a, b);
    }
    cout<<b;
    return 0;
}

#include <iostream>

using namespace std;

int gcd (int a, int b) {

while (a!=0 && b!=0) {

if (a>b) {

a=a%b;

}

else b=b%a;

}

return a+b;

}

int main () {

int t, a, b;

cin>>t>>b;

for (int i=2; i<=t; ++i) {

cin>>a;

b=gcd (a, b);

}

cout<<b;

return 0;

}

Решение задачи

Для решения данной задачи воспользуемся алгоритмом Евклида — алгоритмом нахождения наибольшего общего делителя (НОД) пары целых чисел, т.е. самого большого числа, на которое можно без остатка разделить оба числа, для которых ищется НОД.

Условие задачи на e-olymp
Код решения на ideone

Related Images:

A333. Наибольший общий делитель чисел последовательности

29/11/2016 by Вадим Гордийчук

Примечание: [latex]GCD[/latex] — Greatest common divisor (Наибольший общий делитель, НОД).

Задача

Даны натуральные числа [latex]m[/latex], [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex] [latex]m \ge 2[/latex]. Вычислить [latex]GCD \left( n, \ldots, n_m \right)[/latex], воспользовавшись для этого соотношением [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left( k = 3, \ldots, n \right)[/latex] и алгоритмом Евклида.

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

Количество чисел [latex]m[/latex]; числа [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex].

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

[latex]GCD \left( n_1, \ldots, n_m \right)[/latex].

Тесты

Входные данные					Выходные данные
2	3	4			1
2	4	8			4
4	24	23	40	90	1
4	36	48	20	24	4
3	30	738	1926		6

Код программы

#include <iostream>
using namespace std;

unsigned long long gcd(unsigned long long m, unsigned long long n)
{
    return (n != 0) ? gcd(n, m%n) : m;
}

int main()
{
    unsigned long long m, n, result;
    cin >> m >> result;
    for (unsigned long long i = 2; i <= m; i++)
    {
        cin >> n;
        result = gcd(result, n);
        if (result == 1) m = 1; //same as break
    }
    cout << result << endl;
    return 0;
}

#include <iostream>

using namespace std;

unsigned long long gcd(unsigned long long m, unsigned long long n)

{

return (n != 0) ? gcd(n, m%n) : m;

}

int main()

{

unsigned long long m, n, result;

cin >> m >> result;

for (unsigned long long i = 2; i <= m; i++)

{

cin >> n;

result = gcd(result, n);

if (result == 1) m = 1; //same as break

}

cout << result << endl;

return 0;

}

import java.util.*;

public class Main
{
    public static long gcd(long m, long n)
    {
        if (n != 0)
            return gcd(n, m%n);
        else
            return m;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long m = in.nextLong(), n, result = in.nextLong();
        
        for(long i = 2; i <= m; ++i)
        {
            n = in.nextLong();
            result = gcd(result, n);
            if (result == 1) m = 1; //same as break
        }
        System.out.println(result);
    }
}

import java.util.*;

public class Main

{

public static long gcd(long m, long n)

{

if (n != 0)

return gcd(n, m%n);

else

return m;

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

long m = in.nextLong(), n, result = in.nextLong();

for(long i = 2; i <= m; ++i)

{

n = in.nextLong();

result = gcd(result, n);

if (result == 1) m = 1; //same as break

}

System.out.println(result);

}

Решение задачи

Для решения данной задачи необходимо использовать данную в условии формулу [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left(\right)[/latex].
Также необходимо воспользоваться алгоритмом Евклида для реализации рекурсивной функции [latex]GCD[/latex]:
Пусть [latex]m[/latex] и [latex]n[/latex] — одновременно не равные нулю целые неотрицательные числа и пусть [latex]m \ge n[/latex]. Тогда если [latex]n=0[/latex], то [latex]GCD\left(n, m\right)=m[/latex], а если [latex]n\ne0[/latex], то для чисел [latex]m[/latex], [latex]n[/latex] и [latex]r[/latex], где [latex]r[/latex] — остаток от деления [latex]m[/latex] на [latex]n[/latex], выполняется равенство [latex]GCD\left(m, n\right)=GCD\left(n, r\right)[/latex]. (задача 89 задачника С. Абрамова)
Программа записывает в переменную m число [latex]m[/latex], а в result — [latex]n_1[/latex].
Затем, используя формулу [latex]\left(\right)[/latex], программа до окончания цикла считывает следующие числа из последовательности поверх предыдущих в переменную n и находит сперва [latex]GCD\left(n_1, n_2\right)=x_1[/latex], [latex]GCD\left(x_1, n_3 \right)=x_2[/latex], затем [latex]GCD\left(x_2, n_4\right)=x_3[/latex] и так далее, вплоть до нахождения [latex]GCD[/latex] всех чисел, постоянно записывая новые [latex]GCD[/latex] поверх старых в переменную result. В итоге, программа выводит результирующий [latex]GCD[/latex], который и является ответом.