关于程序设计:算法GCDLCM

GCD

辗转相除得最大公约数。（也叫经典的欧几里得算法）
a,b 两个数，小的那个如果 a，另一个数就变小为 b%a。
而后一直递归上来，就能失去最大公约数 gcd。
code：

int gcd(int a,int b){return b==0?a:gcd(b,a%b);
}

工夫复杂度 logn，十分快。
上面解释下原理：
1. 首先 a，b 哪个先来被模不重要，辗转一次就肯定能失去小的那个了。
2. 而后进行证实：
假如 a =b*c+d
设 a =kA，b=kB。
那么 d =a-bc, 即 d =Ak-Bkc, 提个 k，d=A-B*c。
这个时候 d 肯定是整数，因为整数在 [加，减，乘] 的运算下是关闭的。
所以就模后的数就和除数，被除数有雷同的公约数，就能够有限递推上来了。

LCM

code：

int lcm(int a,int b){return a/gcd(a,b)*b;
}// 就很简略了。。。