一、概念引入

　　GCD，全名Greatest common divisor（最大公因数）。

　　我们以gcd(a,b)或(a,b)表示a与b的最大公因数。

 

　　LCM，全名Least Common Multiple（最小公倍数），

　　我们以lcm(a,b)或[a,b]表示a与b的最小公倍数。

 

二、求最大公约数-欧几里得算法

　　用途：

　　　　求解gcd(a,b)

　　核心公式：

　　　　gcd(a,b) = gcd(b,a mod b)  （其中a mod b > 0)

　　　　或者gcd(a,b) = gcd(c,d) ( 其中a<b,c=max(b,a-b),d=min(b,a-b) )

　　算法思路：

　　　　（保证a>b）

　　　　当a是b的倍数时，a,b最大公约数为b；

　　　　*PS：此时，a mod b = 0，即gcd(a,b) = gcd(b,a mod b) = gcd(b,0) = b，可用于边界判断；

　　　　当a不是b的倍数时，运用核心公式，直到a'是b'的倍数。

　　　　*PS：因为b' = (a mod b) < b，所以a,b两个值在不断调用gcd的过程中将逐渐递减，直至b=0；

　　代码：

1 int gcd(int a,int b) 2 { 3     if(b==0) 4         return a; 5     else  6     { 7         if(a

 

　　*核心公式证法1.

　　　　第一步（证明d是a,b公约数时，d也是b,a mod b的公约数【反应正向进行】）：

　　　　——a可以表示成a = kb + r（a，b，k，r皆为正整数，且r<b），

　　　　——则r = a mod b

　　　　——假设d是a,b的一个公约数，记作 d|a, d|b，即a和b都可以被d整除。

　　　　——而r = a - kb，两边同时除以d，r/d = a/d - kb/d = m，由等式右边（a和b都可以被d整除）可知m为整数，

　　　　——因此d|r，已知r = a mod b

　　　　——综上，d|b 且 d|（a mod b）

　　　　——因此d也是b,a mod b的公约数

 

　　　　第二步（证明d是b,a mod b的公约数时，d也是a,b公约数【反应逆向进行】）：

　　　　——假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数,

　　　　——进而d|a.

　　　　——因此d也是a,b的公约数

　　　　——因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，

 

　　综上,欧几里得算法核心公式得证。

 

三、求最小公倍数 - 大数翻倍法

　　公式法：

　　　　非常简单，∵gcd(a,b) × lcm(a,b) = a × b，

　　　　∴lcm(a,b) = a × b ÷ gcd(a,b)，其中gcd(a,b)可以用求解。

　　大数翻倍法：

　　　　思路也很简单，

　　　　∵lcm(a,b)，同时是a与b的倍数，所以取a，b较大数不断翻倍，直到结果能够整除较小数即可。

1 int lcm(int a,int b) 2 { 3     int i; 4     if(a

四、求最大公约数-Stein算法

　　　　这个算法是针对位数很多的大整数(接近10^10^4)所设计的。未完待续。。。