GCD算法求最大公因数与最小公倍数

1.更相减损法

gcd(a, b) = gcd(b, a-b); //终止条件：a==b -> return a;           

2.辗转相除法

gcd (a, b) = gcd(b, a%b); //终止条件：!(a%b) -> return b;           

3.欧几里得算法

// 非递归算法
// 缩减更相减损法的时间复杂度的同时，避免了辗转相除法的余数溢出问题
int gcd(a, b) {
    int p2 = 1;
  	// 求得a与b共有的、最大的、数值为2^n的因子，并把n保存至p2
    while(!(a&1 || b&1)) {	
        a >>= 1;
        b >>= 1;
        p2 ++;
    }
  	// 求得后，使a与b均除尽2，因为这时至少有一个数已不能被2整除
    while (!a&1) a >>= 1;
    while (!b&1) b >>= 1;
  	// 调整使得总满足a>=b
    if (a<b) {int t = b; b = a; a = t;}
  	// 同时使用“gcd(a,b) = gcd(b,a%b)”与由上代码确保的“至少有一个数不能被2整除”两条性质，完成循环
  	// 退出条件为更迭相减再除二确定的值为奇数（使用最大公约数的数学性质）
    while (!((a=(a-b)>>1) & 1)) {
        while (!a&1) a >>= 1;
        if (a<b) {int t = b; b = a; a = t;}	// 反复交换
    }
    return b << p2;	// 乘回b的2^n，求得真正的最大公约数
}