[TOC]
辗转相除法1
辗转相除法是用来求 greatest common divisor(GCD) 的算法。
def gcd(a:int,b:int)->int:
if not b: return a
else:
return gcd(b,a%b)
原理解析2
对于任何可以整除a和b的整数，那么它也一定能整除a-b（和b)，因此我们选择该整数（前面提到的任何整数）为gcd(a,b)，它一定比a-b和b的最大公约数小：gcd(a,b)<=gcd(a-b,b)
同理，任何可以整除a-b和b的整数，一定可以整除a和b，因此我们选择该整数为gcd(a-b,b)，它一定比a和b的最大公约数小：gcd(a-b,b)<=gcd(a,b)
由此可知：gcd(a,b)=gcd(a-b,b)
因为总有整数n，使得 a - n*b = a mod b，所以迭代可知：
gcd(a-b,b)=gcd(a-2b,b)=…=gcd(a-n*b,b)=gcd(a mod b,b)
时间复杂度
\[O(lg min(a,b))\]最小公倍数 LCM
least common multiple
lcm(a,b) = a*b / gcd(a,b)
