欧几里得算法
function Euclid(a;
b)
1: if b = 0 then
2: return a;
3: end if
4: return Euclid(b;
a mod b);
复杂度分析：
设 a>=ba >= b ，则有 amodb
假设a=bq+ra = b q + r ，其中q>=1q >= 1 ，且 0<=r
r=a?bq
因此：
a
11+q×a
==> aq1+q?bq<0a q 1 + q ? b q < 0
==> aq1+q+a1+q?bq
所以有： a?bq
于是复杂度为： min(O(loga),O(logb))m i n ( O ( l o g a ) , O ( l o g b ) )即O(logn)
