YoungProgrammer

Lesson: 23
Problem: 1528
Title: Least Common Multiple
Difficulty Level: 2.0
Date: FEB 27, 2009
Site: http://acm.tju.edu.cn/toj/

Given a set of integers, you have to find LCM.

How to find LCM of more than two numbers ? Very easy, Lets given integer

set is: 5, 8, 30

LCM(5,8) = 40

LCM(40,30) = 120
So, LCM(5,8,30) = 120

How to find LCM of two numbers ?
We know N X M = GCD(N,M) X LCM(N,M) where N and M are two integers.

Then, LCM(N,M) = (N X M) / GCD(N,M)

As we can find GCD(N,M) , then we also able to find LCM(N,M) very easily.


Source Code:

#include<stdio.h>

long long gcd(long long a, long long b) { return b ? gcd(b,a%b) : a; }


void Cal(long long n) {
	long long i, pre = 1, m, gd;

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

		scanf("%lld",&m);
		pre = (m*pre)/gcd(pre,m);

	}
	printf("%lld\n",pre);
}
int main() {

	long long kase, n;
	scanf("%lld",&kase);

	while(kase--) {
		scanf("%lld",&n);

		Cal(n);
	}
	return 0;
}

Note: long long is 64-bit signed integer.