牢记gcd最大公因数和lcm最小公倍数数论

由于不会辗转相除法，在不能带资料的比赛中肯定会吃亏。上次天体报名赛就现场找规律写了个gcd，虽然过了但是很丢人啊啊啊。。
直接进入正题，gcd有以下恒等式：gcd(a, b) = gcd (a, a mod b)，并且边界条件gcd(a, 0) = a; 这里假设a>=b
于是gcd函数就出来了

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

至于最小公倍数lcm，也有一个恒等式，lcm(a, b) * gcd(a, b) = a * b;
证明一下：由唯一分解定理，设a = p1 ^ e1 * p2 ^ e2 *... * pr ^ er,
b = p1 ^ f1 * p2 ^ f2*... * pr ^ fr
gcd(a, b) = p1 ^ min(e1, f1) * p2 ^ min(e2, f2) * ... * pr ^ min(er, fr)
lcm(a, b) = p1 ^ max(e1, f1) * p2 ^ max(e2, f2) * ... * pr ^ max(er, fr)
所以恒等式lcm(a, b) * gcd(a, b) = a * b得证。
所以求lcm的方式就出来了，lcm(a, b) = a * b / gcd(a, b)
不过这里要注意，做乘法再做除法会有溢出的风险
所以应该写成 lcm(a, b) = a / gcd(a, b) * b
【牢记gcd最大公因数和lcm最小公倍数】