$\Huge\color{orchid}{点击此处获取更多干货}$

辗转相除法

最大公约数$(\text{gcd})$求解用到的辗转相除法应该也是小学数学中就提到过的了，其步骤如下：
1. 两个数$a,b$，让较大的成为被除数，较小的成为除数
2. 执行一次除法得到余数，成为新的除数，并且让上一轮的除数成为新的被除数
3. 如果此时除数为0，那么被除数就是最大公约数，否则回到步骤2

原理可以用下面的递推式表示：
$gcd(a,b)=\left\{\begin{matrix}a,b=0 \\gcd(b,a\%b),b\ne 0\end{matrix}\right.$

至于为什么，可以假设$a=k*b+r$，其中$r=a\%b$。假设两个数有一个公约数$d$，即$a,b$都能整除$d$，由于$r=a-k*b$，故$r/d=a/d-k*(b/d)$，在先前的条件下，可以得知$r/d$也是整数，即$r$可以整除$d$，$d$是$a,b,r$三数的公约数，因此$b$不为0的情况下，$gcd(a,b)=gcd(b,a\%b)$

C++ 代码

迭代法：

/**
 * @brief 最大公约数（迭代）
 * 直接按照流程写代码，直观清晰
 * @warning 需要保证a >= b（按照惯例应该抛出异常，这里偷懒省略了）
 */
int gcd(int a, int b) {
    int r;
    while(b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

递归法：

/**
 * @brief 最大公约数（递归）
 * 代码简短，但需要事先推导出递推公式
 * @note 有个很“优雅”的“单行式”写法（非主流，不建议各位模仿）：
 *  @code 
 *      return (b == 0) ? a : gcd(b, a % b);
 *  @endcode
 */
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}