关于最大公约数的求解，主要有欧几里得算法和Stein算法两种方法。

欧几里得算法

欧几里得算法的原理为：

若

\[a \equiv r(mod\ b)\]

则

\[gcd(a,b) = gcd(b,r)\]

算法执行过程为辗转相除法。

递归形式：

/**
 * 求解 a, b 两个数的最大公约数。
 */
int gcd(int a, int b)
{
    if(b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

非递归形式：

/**
 * 求解 a, b 两个数的最大公约数。
 */
int gcd(int a, int b)
{
    while(b > 0) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

欧几里得算法的时间复杂度为 $O(\log{n})$，最坏情形为斐波那契数列的相邻两项。空间复杂度为 $O(1)$。

Stein算法

Stein算法是另一种求解两个数的最大公约数的算法。其原理为：

\[gcd(ka, kb) = k \times gcd(a, b)\]

Stein算法的实现如下：

/**
 * Stein算法
 *
 * 条件：0 <= b < a.
 */
int gcd(int a, int b)
{
    int r = 0;
    while(b > 0) {
        if(a&0x01 == 0 && b&0x01 == 0) { // a, b 都为偶数
            a >> 1; b >> 1; r = r + 1;
        }
        else if(a&0x01 == 0 && b&0x01 == 1) { // a 偶，b 奇
            a >> 1;
        }
        else if() { // a 奇，b 偶
            b >> 1;
        }
        else if() { // a 奇，b 奇
            a = (a-b) >> 1;
        }

        if(a < b) {
            a ^= b; b ^= a; a ^= b; // swap(a, b);
        }
    }
    return a<<r;
}

与欧几里得算法相比，Stein 算法的优点在于不需要对大整数进行取模运算，只需要进行移位和减法运算。