欧几里德(最贵族约数)
欧几里德(最大公约数)也就是常说的辗转相除法。最早我们理解的都是通过减法实现的，如下面递归方式：long gcd
欧几里德(最大公约数)
也就是常说的辗转相除法。
最早我们理解的都是通过减法实现的，如下面递归方式：
long gcd (long a, long b){ while (b>0) { long r = a%b; a = b; b = r; } }实现起来虽然比较简单，原理却不是一下就能想通。
因此推导一下，如果a>b>0， 且r=a%b。
a = b*k + r
若d为a和b的一个约数，则d也是r的一个约数
即：
a = d*k1
b = d*k2
r = a - b*k = d*k1 - d*k*k2 = d*(k1 - k*k2)
d|b, d|a <-> d|r
然后就有：
(d|a)∧(d|b) <-> (d|b)∧(d|r), ∧表示同时成立。
找到第一个d就是最大公约数了，当k=1的时候就是减法的特例了。
复杂度方面有个推论：O(lg(n)), n=max(a, b)
