『算法-ACM 竞赛-数学-数论』最小公倍数+最大公约数

数学中约定：
GCD（a，b)为 a ,b 的最大公因数 LCM（a，b）为小公倍数

必须要知道的公式:

a*b = gcd(a,b) * lcm (a,b)

先说 GCD 怎么求：

int gcd(int a,int b){
	return __gcd(a,b); //不是我闹着玩，是真有这个函数
}

正经的来了，欧几里得算法

int gcd(int a,int b){
	if(b==0) return a;
	else return gcd(b,a%b);
}

if-else 比较慢，三目运算符优化：

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

肯定不会爆栈，再给一种非递归算法：

int gcd(int  a, int  b){
    int  t;
    while(b){
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

接下来就是最小公倍数了：
$LCM（a，b）=a * b/GCD（a,b)$
但是要是 a*b 爆了 long long 咋整？
我们使用数学交换律大法：
$LCM(a,b)=a /GCD(a,b)*b$
因为 GCD 一定是 a 或 b 的因子，所以上面的等式成立。