GCD
GCD，也就是最大公约数，即两个数拥有的相同的因数集中最大的一个。
求法
如果求任意两个数的GCD呢，相信小学的时候都学过辗转相除法，也就是欧几里得算法，当然还有以前学过的更相减损术，这里只讨论欧几里得算法（据说更相减损术是欧几里得算法的特殊情况）。
欧几里得算法
描述
欧几里得算法的内容是：
两个数的最大公约数是指能同时整除它们的最大正整数。
设两数为$a,b(a\geq b)$，求a和b最大公约数gcd(a,b)的步骤如下：
Ⅰ.用a除以b，$a\geq b$，得$a \div b=q…r_1(0\leq r_1)$。
Ⅱ.若$r_1=0$，则$gcd(a,b)=b$；
Ⅲ.若$r_1\neq 0$，则再用$b\div r_1=q…r1(0\leq r_1)$。
如此往复，直到余数为0，那么gcd(a,b)为除数。
证明
证明欧几里得算法，也就是证明：
Ⅰ.$gcd(a,b)==gcd(b,a\mod b)$.
Ⅱ.所求为最优.
Ⅰ
首先设c为a,b的公因数，则设$a=m\times c,b=n\times c$。
设$a=k\times b+r$，则得到$r=a-k\times b=m\times c-k\times n\times c=(m-k\times n)\times c$。
则c也为b和r的公因数。
再者，设b和r的公因数为v，则设
$b=i\times v$
$r=j\times v$
于是有$a=k\times b+r=k\times i\times v+j\times v=(k\times i+j)\times v$。
则a和b的公约数也为v.
综上我们可以使用这个递推。
Ⅱ
下面我们来推一下:
$a\mod b=r$
$b\mod r=r_1$
$r\mod r_1=r_2$
……
$r_{n-3}\mod r_{n-2}=r_{n-1}$
$r_{n-2}\mod r_{n-1}=r_n$
由于$a\geq b\geq 0$那么$r_1….r_n$是递减的，最终将变为0.
则当$r_{n-1}\neq 0,r_n==0$时，可以得到$r_{n-1}|r_{n-2}$（’|’为整除符号，a|b代表b能被a整除），则$r_{n-2}和r_{n-1}$的公约数只有$r_{n-1}和r_{n-1}的约数$，其中最大的就是$r_{n-1}$。
代码实现
接下来给出代码实现
1 | int gcd(int x, int y){ |
LCM
聊完GCD，再来聊聊LCM，也就是最小公倍数,即两个数公共的倍数集合中最小的元素。
求法
对于两个数a,b,有公式:
$a\times b=lcm(a,b)\times gcd(a,b)$。
证明
设$x=gcd(a,b)$；
则$n=a/x,m=b/x$。显然a和m是互素的，所以$lcm(n,m)=n\times m$,又因为$lcm(a,b)=lcm(n\times x,m\times x)=x\times n\times m$。
所以$lcm(a,b)=gcd(a,b)\times a/gcd(a,b)\times b/gcd(a,b)$，即$lcm(a,b)\times gcd(a,b)=a\times b$
代码实现
1 | int lcm(int a, int b){ |
