求最小公因数和最大公倍数

今天从算法竞赛的书上看到求这两个东西的方法，稍微记一下。

根据欧几里得算法，即著名的辗转相除法：

gcd(a,b)=gcd(b,a%b)，边界条件为当b=0时,gcd(a,b)=a;

（扩展欧几里得请看另一篇博客）

int gcd(int x,int y){return y?gcd(y,x%y):x;}

那么，最小公倍数也是这么求的。

假如我们要求a,b的最小公倍数，我们先把他们拆成若干质数的积：（以下未用markdown）

a=p₁^e₁p₂^e₂···p_n^e_n

b=p₁^f₁p₂^f₂···p_n^f_n 

那么

gcd(a,b)=p₁^{min(e₁,f₁)} ···p_n^min(e_n,f_n)

lcm(a,b)=p₁^{max(e₁,f₁)} ···p_n^max(e_n,f_n)

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