输入包含多个测试实例,每个测试实例的开始是一个正整数n,然后是n个正整数.
为每组测试数据输出它们的最小公倍数,每个测试实例的输出占一行.你可以假设最后的输出是一个32位的整数.
我这里用欧几里德算法:对任意非负数a 和 任意正整数b
有很多人喜欢打破沙锅问到底,曾经很多人也问过我gcd算法的原理,下面是GCD递归定理的证明.
下面提到的 a|b 就是表示a能被b整除.
首先我们来看一下两条定理,都很好理解的.
即(a mod b)是a与b的线性组合.
由①式得:
运用定理②,再根据③④就可以完成GCD定理的证明.