5. 欧几里得算法(辗转相除法) ---- O(logn)O(logn)
最大公约数表示： gcd(a, b) 或 (a, b)
最小公倍数表示： lcm(a, b) 或 [a, b]
0和任何一个数的最大公约数都是那个数本身

理论基础： (a,b) = (b, a mod b) --- 理论上证明：最多转化logn次

求最大公约数

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
证明：
(a, b) >= (b, a mod b)   
设(b, a mod b)公约数为d
令 a = kb + r  则 a mod b = r;
因为 d | b 且 d | r
所以 d | a

(a, b) <= (b, a mod b)
因为 d | a 且 d | b 
所以 d | r

所以 (a, b) = (b, a mod b)
求最小公倍数

int lcm(int a, int b){
    return a * b / gcd(a, b);
}
典型例题
最大公约数