【目的】
计算两个非负整数a，b的最大公约数
例如：12 和 8 的最大公约数为 4
【代码模板】
int GCD(int a, int b){
return b == 0 ? a : GCD(b, a % b);
}
在#include库中包含了__gcd(a, b)函数可以直接调用
【相关原理】
欧几里得算法、辗转相除法、更相减损术。
欧几里得算法 又称 辗转相除法，而 辗转相除法 是 更相减损术 的 优化
计算公式gcd(a, b) = gcd(b, a % b)
【思路】
假设有两个数161和63，计算这两个数的最大公约数。
- 设这个最大公因数为m可以将较大的数161看成63+98，63与98的和161可以被m整除，其中63也可以被m整除，自然98可以被m整除问题就转换为求98和63的最大公因数m（和上面m相等）可以将98看成63+35，其中63可以被m整除，和98也能被m整除，故35也可以被m整除所以问题进一步转换为求35和63的最大公因数m（和上面m相等）同理转换为求 (63-35)=>28和35 的最大公因数然后转换为求28和7的最大公因数…（一直相减）后来转换为求7和7的最大公因数，最后转换为求7和0的最大公因数输出第一个数字即可
这就是相减损术的原理
我们发现求28和7的最大公约数，一直减7，一直减7…减到不能减为止
这个不断减7的过程就是除7求余数（即%7）
这样我们可以将相减损术优化成辗转相除法
最小公倍数(Least Common Multiple)
【目的】
计算两个非负整数a，b的最小公倍数
例如：12 和 8 的最小公倍数为 24
【代码模板】
int LCM（int a, int b){
return a * b / GCD(a, b);
}
【相关原理】
分解质因数： 每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。
【思路】
用这两个数的乘积除以最大公约数即可。
假设求 12 和 8 的最小公倍数
我们先将 12 和 8 进行分解质因子：
12 = 2 x 2 x 3
8 = 2 x 2 x 2
这里可以看到 12 和 8 的相同质因子是 2 x 2 也就是 12 和 8 的最大公约数
GCD(12, 8) = 4 = 2 x 2
所以这里可以看成在 12 和 8 相乘的时候多乘了一个最大公约数 4 = (2 x 2)
12 x 8 = (2 x 2 x 3) x (2 x 2 x 2)
所以要约掉一个最大公约数，剩下的 2 x 2 x 3 x 2 = 24 就是 12 和 8 的最小公倍数，因为2 x 2 x 3 x 2中无论去除哪一个数都会导致不能整除 12 或 8
