2028 Lowest Common Multiple Plus
求n个数的最小公倍数.
输入包含多个测试实例,每个测试实例的开始是一个正整数n,然后是n个正整数.
为每组测试数据输出它们的最小公倍数,每个测试实例的输出占一行.你可以假设最后的输出是一个32位的整数.
最小公倍数lcm(x, y) = x * y / gcd(x, y) (其中gcd()求最大公约数)
所以这题的关键的关键是求最大公约数.
我这里用欧几里德算法:对任意非负数a 和 任意正整数b
gcd(a, b) = gcd(b, a mod b)
有很多人喜欢打破沙锅问到底,曾经很多人也问过我gcd算法的原理,下面是GCD递归定理的证明.
下面提到