C++ 辗转相除法（欧几里得算法）完整教程

一、原理介绍

辗转相除法用于求两个正整数最大公约数（GCD，Greatest Common Divisor）

核心公式

规则：

1. 设 $a>b$，计算余数 $r = a \% b$
2. 令 $a=b,\;b=r$，重复取余
3. 当余数 $b=0$ 时，此时的 $a$ 就是最大公约数

示例：求 $\gcd(24,18)$ $\gcd(24,18)=\gcd(18,6)=\gcd(6,0) \implies \boldsymbol{6}$

拓展：最小公倍数 $\text{LCM}(a,b) = \dfrac{a\times b}{\gcd(a,b)}$

二、实现方式（3种常用写法）

方式1：递归实现（代码最简）

#include <iostream>
using namespace std;

// 递归版欧几里得算法
int gcd(int a, int b)
{
    // 终止条件：b等于0，a就是最大公约数
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main()
{
    int x, y;
    cout << "请输入两个整数：";
    cin >> x >> y;
    cout << "最大公约数 = " << gcd(x, y) << endl;
    return 0;
}

⚠️ 注意：递归层数极浅，不用担心栈溢出。

方式2：循环迭代实现（竞赛推荐，效率稳定）

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    // 只要余数不为0，持续循环
    while (b != 0)
    {
        int rem = a % b; // 保存余数
        a = b;
        b = rem;
    }
    return a;
}

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

方式3：C++17 标准库内置函数（最简代码）

<numeric> 头文件提供 std::gcd

注意：部分编译器需要开启C++17标准，负数需要自行预处理

#include <iostream>
#include <numeric>  // std::gcd
using namespace std;

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

三、完善增强版：支持负数 + 最小公倍数计算

#include <iostream>
#include <cmath>
using namespace std;

// 通用GCD：自动处理负数
long long gcd(long long a, long long b)
{
    a = abs(a);
    b = abs(b);
    while (b != 0)
    {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 最小公倍数 LCM
long long lcm(long long a, long long b)
{
    if(a == 0 || b == 0) return 0;
    return a / gcd(a, b) * b; // 先除后乘，防止溢出
}

int main()
{
    long long x, y;
    cin >> x >> y;
    cout << "最大公约数：" << gcd(x, y) << endl;
    cout << "最小公倍数：" << lcm(x, y) << endl;
    return 0;
}

✅ 优化点：a/gcd*b 代替 a*b/gcd，避免大数相乘溢出。

四、常见易错点

1. 大小顺序无关：gcd(18,24) 和 gcd(24,18) 结果一致，a%b 自动处理
2. 不能传入0：gcd(0, x) 结果为 $|x|$；两个0无意义
3. 负数问题：取模结果带符号，函数内部务必先用 abs()
4. 数据溢出：竞赛大数建议使用 long long 代替 int

五、拓展：拓展欧几里得算法（求不定方程 ax+by=gcd(a,b)）

如果你后续需要求逆元，可以直接使用拓展版：

#include <iostream>
using namespace std;

// 拓展欧几里得
long long exgcd(long long a, long long b, long long &x, long long &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    long long a, b, x, y;
    cin >> a >> b;
    long long g = exgcd(a, b, x, y);
    cout << "gcd=" << g << " 一组解 x=" << x << " y=" << y << endl;
    return 0;
}