辗转相除法

原理

$$ gcd(a,b)=gcd(a\space mod\space b,a) $$

为了使这个等式有计算意义，我们假定a > b。

代码

    public static long divisionGcd(long m, long n) {
        while(n != 0) {
            long rem = m % n;
            m = n;
            n = rem;
        }
        return m;
    }

这里我们不要求m ≥ n，因为如果m < n，一次迭代相当于m，n进行了一次交换。

时间复杂度

这个算法的时间复杂度为O(logN)，一个较粗略的证明方法是：

引理1：如果一个算法能在O(1)时间内将问题的规模减小为原来的一半，则这个算法的时间复杂度是O(logN)。

引理2：若a, b > 0

$$ a\space mod\space b < \frac a2 $$

证明：分情况讨论：

如果b < a/2，显然余数小于b，即小a/2。

如果b ≥ a/2，我们有a mod b = a mod (a - b)，转化为第一种情况。

有以上两个引理，不难证明经过两次迭代，问题的规模最少减小一半，从而可以证明这个算法的时间复杂度上界是O(logN)。