关于程序设计:算法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;}//就很简略了。。。