问题描述
Problem Description
求n个数的最小公倍数。
Input
输入包含多个测试实例，每个测试实例的开始是一个正整数n，然后是n个正整数。
Output
为每组测试数据输出它们的最小公倍数，每个测试实例的输出占一行。你可以假设最后的输出是一个32位的整数。
Sample Input
2 4 6
3 2 5 7
Sample Output
12
70
问题分析
Problem Analyse
本题是为C语言初学者提供的。
Algorithm Analyse
最小公倍数lcm(x, y) = x * y / gcd(x, y) (其中gcd()求最大公约数)
所以这题的关键的关键是求最大公约数。
算法实现
我这里用欧几里德算法：对任意非负数a 和 任意正整数b
gcd(a, b) = gcd(b, a mod b)
有很多人喜欢打破沙锅问到底，曾经很多人也问过我gcd算法的原理，下面是GCD递归定理的证明。
下面提到的 a|b 就是表示a能被b整除。
首先我们来看一下两条定理，都很好理解的。
- d|a 并且 d|b 蕴含着 d|(ax + by) ①
- a|b 且 b|a 蕴含着 a = ±b ②
从上述②式就可以看出，只要证明gcd(a, b) 与 gcd(b, a mod b)可以互相整除，就能证明它们相等。先来证明gcd(a, b) | gcd(b, a mod b)。
设d = gcd(a, b)
=>
1. d|a
2. d|b
∵(a mod b) = a - q×b; (q = 「a/b」)
即(a mod b)是a与b的线性组合。
由①式得:
d | (a - q×b) <==> d | (a mod b)
由①式得:
d | gcd(b, a mod b) <==> gcd(a, b) | gcd(b, a mod b) ③
证明gcd(b, a mod b) | gcd(a, b)。
设d = gcd(b, a mod b)
=>
1. d|b
2. d|(a mod b)
∵a = (a mod b) + q×b; (q = 「a/b」)
即 a 是b与(a mod b)的线性组合。
由①式得:
d | a
∵d | b
由①式得:
d | gcd(a, b) <==> gcd(b, (a mod b)) | gcd(a, b) ④
运用定理②，再根据③④就可以完成GCD定理的证明。