135. НОК

 

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

 

Вход. В первой строке задано количество чисел n (1 < n < 21). Во второй строке находится n натуральных чисел, не превышающих 100 и разделенных пробелом.

 

Выход. НОК заданных чисел.

 

Пример входа

Пример выхода

2

2 3

6

 

 

РЕШЕНИЕ

НОД, НОК

 

Анализ алгоритма

Поскольку входных чисел не более 20, каждое из которых не больше 100, то их НОК может выходить за пределы 64 битового целочисленного типа. Поэтому следует воспользоваться длинной арифметикой.

Покажем, как вычислить res = НОК(m1, m2, …, mn), совершив минимум операций над большими числами (значение res является большим). Переберем все пары (mi, mj), i < j, для каждой пары вычислим d = НОД(mi, mj), после чего разделим mj на d. После этого произведение оставшихся mi равно значению res.

 

Пример

Рассмотрим процесс вычисления res = НОК(2, 12, 6, 24, 3). Запустим двойной цикл перебора всех пар (mi, mj) и сокращения mj на d:

После перебора пар (m1, mj) = (2, mj) массив m будет содержать числа (2, 6, 3, 12, 3).

После перебора пар (m2, mj) = (6, mj) массив m будет содержать числа (2, 6, 1, 2, 1).

После перебора пар (m3, mj) = (1, mj) массив m будет содержать числа (2, 6, 1, 2, 1).

После перебора пар (m4, mj) = (2, mj) массив m будет содержать числа (2, 6, 1, 2, 1).

По окончанию двойного цикла вычисляем произведение всех чисел, содержащихся в массиве m. Оно равно res = НОК(2, 12, 6, 24, 3) = 2 * 6 * 1 * 2 * 1 = 24.

 

Реализация алгоритма

Входные числа будем хранить в массиве m.

 

scanf("%d",&n);

for(i = 0; i < n; i++) scanf("%d",&m[i]);

 

Чтобы избежать длинного деления, выполним обработку чисел в массиве m, как указано в анализе задачи.

 

for(i = 0; i < n; i++)

for(j = i + 1; j < n; j++)

{

  temp = gcd(m[i],m[j]);

  m[j] /= temp;

}

 

Перемножим числа, которые находятся в массиве m. Число res является большим.

 

BigInteger res;

for(res = 1, i = 0; i < n; i++)

  res = res * m[i];

 

Выводим ответ.

 

res.print(); printf("\n");

 

Java реализация

 

import java.util.*;

import java.math.*;

 

public class Main

{

  public static int gcd(int a, int b)

  {

    return (b == 0) ? a : gcd(b,a % b);

  }

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int m[] = new int[n];

    for(int i = 0; i < n; i++)

      m[i] = con.nextInt();

  

    for(int i = 0; i < n; i++)

    for(int j = i + 1; j < n; j++)

    {

      int temp = gcd(m[i],m[j]);

      m[j] /= temp;

    }

   

    BigInteger res = new BigInteger("1");

    for(int i = 0; i < n; i++)

      res = res.multiply(BigInteger.valueOf(m[i]));

   

    System.out.println(res);

  }

}

 

Java реализация – класс BigInteger

Непосредственное вычисление res = НОК(m1, m2, …, mn).

 

import java.util.*;

import java.math.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    BigInteger res = BigInteger.ONE;

    for(int i = 0; i < n; i++)

    {

      BigInteger x = con.nextBigInteger();

      res = res.multiply(x).divide(res.gcd(x));

            // res = res * x / gcd(res,x)

    }

   

    System.out.println(res);

    con.close();

  }

}

 

Реализация при помощи вектора.

 

import java.util.*;

import java.math.*;

 

public class Main

{

  public static int gcd(int a, int b)

  {

    return (b == 0) ? a : gcd(b,a % b);

  }

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    Vector<Integer> m = new Vector<Integer>();

    for(int i = 0; i < n; i++)

      m.add(Integer.valueOf(con.nextInt()));

 

    for(int i = 0; i < n; i++)

    for(int j = i + 1; j < n; j++)

    {

      int temp = gcd(m.get(i),m.get(j));

      m.set(j,Integer.valueOf(m.get(j)/temp));

    }

   

    BigInteger res = new BigInteger("1");

    for(int i = 0; i < n; i++)

      res = res.multiply(BigInteger.valueOf(m.get(i)));

  

    System.out.println(res);

  }

}