算法|数论之欧几里德算法（一）算法|数学

简介：
欧几里德算法，又称辗转相除法，是求解最大公约数的算法。
定理：
欧几里德算法的理论支撑为GCD递归定理，下面介绍这个定理。
GCD递归定理：
对任意非负整数a和任意正整数b，gcd(a , b) = gcd(b , a%b)
代码：
由上述定理，我们可以直接得出gcd函数的代码：

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

【算法|数论之欧几里德算法（一）】扩展：
根据a，b的最大公约数，我们可以求得a，b的最小公倍数。
lcm函数：

int lcm(int a,int b){ return a/gcd(a,b)*b; }

算法|数论之欧几里德算法（一）