最大公约数

辗转相除法

辗转相除法，又名欧几里得算法（Euclidean Algorithm)，是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，知道最后余数是 0 为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

辗转相除法首次出现于欧几里得的《几何原本》（第 VII 卷，命题 i 和 II）中，而在中国则可以追溯至东汉出现的《九章算术》。

两个数的最大公约数是指能同时整除它们的最大正整数。
辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的 5 倍。拉梅于 1844 年证明了这点，同时也标识这计算复杂性理论的开端。
三个数的最大公约数的定义和两个数的相同，即是它们共有的素因数的积，它们或者也可以按下式计算：
$GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b)$
所以，欧几里得的辗转相除法实际上可以计算任意多整数的最大公约数。

数学上的应用

贝祖等式
主理想和相关问题
扩展欧几里得算法
矩阵法
欧几里得引理和唯一分解
线性丢番图方程
乘法逆和 RSA 算法
中国剩余定理
连分数
整数分解算法

#include<iostream>
using namespace std;

int GCD(int a, int b)
{
    if(b == 0) return a;
    else return GCD(b, a%b);
}

int main()
{
    int a, b;
    cin >> a >> b;
    cout << GCD(a, b) << endl;
    return 0;
}

最大公约数