欧几里德(最大公约数)
也就是常说的辗转相除法。

最早我们理解的都是通过减法实现的，如下面递归方式：

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)