任务
求两个数a,b的最大公约数gcd(a,b)。
说明
由贝祖定理得，gcd(a,b)=gcd(b,a-b)，其中a>=b。通过这样不断的迭代，直到b=0，a就是原来数对的最大公约数。考虑到只使用减法会超时，我们观察到如果a-b4仍然大于b的话，要进行一次同样的操作，就把a减到不足b为止，所以gcd(a,b)=gcd(b,a mod b)。由此可以在log的时间内求出两个数的gcd。由贝祖定理得，gcd(a
阅读背景：
算法学习笔记1.2.1 欧几里得算法
来源：互联网
分享到：
