最大公因数gcd与最小公倍数lcm
- 第一步当然要说一说定义啦
定义：找到一个最大的数g，使得g|a，g|b，则g=gcd（a,b）
找到一个最小的数l，使得a|l，b|l，则l=lcm(a,b)
注：“g|a”表示g整除a
- 众所周知，最大公因数与最小公倍数有一个常用结论
即 gcd(a,b) * lcm(a,b)=a * b
那么它是怎么来的呢（思考两分钟）
下面让我们来简易证明一下：
证明：设最大公因数为g，最小公倍数为l；
由定义可知g|a && g|b；
即 a,b均可写作 a=g * a1，b=g * b1
那么gcd(a1,b1)=1-->why? (感性理解一下：如果这两个数的最大公约数不等于1的话，那么gcd（a，b）它一定不等于g，而为gcd(a1,b1) * g。也就是说如果g为a,b的gcd，那么gcd(a1,b1)一定等于1）
由lcm的定义可知 l=a * a2=b * b2；
由已证可知 l=g * a1 * a2=g * b1 * b2；
我们单独拿出g * a1 * a2=g * b1 * b2这一部分；
两边同时约去g可得到 a1 * a2=b1 * b2；
且易知只有a2=b1；b2=a1时此式成立，且l尽量小
再将此结论带入得
l=g * a1 * b1；
又因为gcd(a,b)=g
所以gcd(a,b) * lcm(a,b)=g^2 * a1 * b1=g * a1 * g * b1=a * b;
证毕；
所以，以后凡是有任何问题让求两个数的最小公倍数的时候，在已知gcd（a,b）的情况下，可以转为lcm（a,b）=(a * b)/gcd(a,b);
那么接下来当然就要说一下gcd（a,b）到底怎么求
介绍一种常用的方法
辗转相除法(欧几里得算法)
gcd(a,b)=gcd(b,a-b);(假设a>b)
应用多次（假设应用n次）得到gcd（a,b）=gcd(b-a-n * b)
即可以得到:
gcd(a,b)=gcd(b,a%b);(相当于多次减法一起应用)
约定 gcd(a,0)=gcd(0,a)=a;
附上代码
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
那么计算gcd（a,b）的复杂度是多少
由上可知我们的计算过程是gcd（a,b）=gcd（b,a%b）
假设a>b 那么a%b一定小于a/2;
如果b<=a/2 又因为a%b<b即小于a/2;
如果b>a/2 那么a%b=a-b(因为此处商只能是1) 因为a-b<a/2,所以a%b<a/2;
所以无论b取什么值，a%b始终小于a/2;
换句话说，我们的每一次操作，都会使较大数变成较大数原来的一半以下
所以最多做log n次操作
即计算gcd（a,b）的复杂度是log n的
思考计算gcd（a1,a2,a3,...,an）的复杂度是多少呢
n log n?其实并不是的
显而易见，当我们算出gcd(a1,a2)=g，之后再次求gcd的话，是用g与a3求出新gcd的值，即gcd(g,a3).因此在算g与a3的最大公因数时，因为你的最大公因数是会越来越小的，因此，得到的复杂度并不是log a3，而是log g.
因此，计算gcd(a1,a2,a3,...,an)的复杂度应该是O（n+log n）.
在这里，第一个n表示要枚举a1到an;
Log n代表的需要将每一个最大公因数不断地折半，最后来得到结果。
最后补充一点：如要求lcm(a,b,c)，我们先要将其转换成lcm[lcm(a,b),c]再进行求解;
注意：lcm(a,b,c)≠(a*b*c)/(g^2);