135. LCM

 

Find the Lowest Common Multiple of n positive integers.

 

Input. The first line contains number n (1 < n < 21). The second line contains n positive integers, separated by a space. All integers are not greater than 100.

 

Output. The Lowest Common Multiple of n given numbers.

 

Sample input

2

2 3

 

Sample output

6

 

 

SOLUTION

LCM

 

Algorithm analysis

Since the amount of input number is no more than 20, each of which is no more than 100, their LCM may be beyond the 64-bit integer type. Therefore, we should use the long arithmetic.

We show how to calculate res = LCM(m1, m2, …, mn) performing a minimum operations on big integers (the value res will be big integer). Iterate through all pairs (mi, mj), i < j, for each pair calculate d = GCD(mi, mj), then divide mj by d. After that, the product of remaining mi equals to the value of res.

 

Example

Consider the process of computing res = LCM(2, 12, 6, 24, 3). Run the double loop through all the pairs (mi, mj) and reducing mj on d:

After iterating through all pairs (m1, mj) = (2, mj) the array m will contain the numbers (2, 6, 3, 12, 3).

After iterating through all pairs (m2, mj) = (6, mj) the array m will contain the numbers (2, 6, 1, 2, 1).

After iterating through all pairs (m3, mj) = (1, mj) the array m will contain the numbers (2, 6, 1, 2, 1).

After iterating through all pairs (m4, mj) = (2, mj) the array m will contain the numbers (2, 6, 1, 2, 1).

At the end of double loop calculate the product of all the numbers contained in the array m. It equals to res = LCM (2, 12, 6, 24, 3) = 2 * 6 * 1 * 2 * 1 = 24.

 

Algorithm realization

Input numbers will be stored in the array m.

 

scanf("%d",&n);

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

 

To avoid the long division, process the numbers in array m, as indicated in the problem analysis.

 

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

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

{

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

  m[j] /= temp;

}

 

Multiply the numbers in array m. The number res must have the BigInteger type.

 

BigInteger res;

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

  res = res * m[i];

 

Print the answer.

 

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

 

Java realization

 

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

  }

}

 

Realization using vector

 

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

  }

}