• C++
  • C++ 辗转相除法(欧几里得算法)完整教程

  • @ 2026-7-31 20:07:43

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

一、原理介绍

辗转相除法用于求两个正整数最大公约数(GCD,Greatest Common Divisor)

核心公式

gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b) = \gcd(b,a \bmod b)

规则:

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

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

拓展:最小公倍数 LCM(a,b)=a×bgcd⁡(a,b)\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∣|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;
}

3 条评论

  • @ 2026-10-9 19:21:36

    C++14 环境下 GCD

    C++14 没有标准 std::gcd(std::gcd 是C++17才加入 <numeric>)

    方案1:GCC扩展 __gcd(C++14可用,信奥/GESP GCC)

    头文件:<algorithm>

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        cout << __gcd(24,18) << endl;
        return 0;
    }
    

    ⚠️ 限制:

    1. 仅GCC支持,MSVC不支持
    2. 参数建议非负,负数结果异常,最好套abs:__gcd(abs(a),abs(b))
    3. __gcd(0,0) 未定义行为
    4. 两个参数类型必须相同

    方案2【最推荐,C++14万能,跨编译器】手写欧几里得

    #include <iostream>
    using namespace std;
    
    int gcd(int a, int b)
    {
        while(b != 0)
        {
            int rem = a % b;
            a = b;
            b = rem;
        }
        return a;
    }
    
    int main()
    {
        cout << gcd(24,18) << endl;
        return 0;
    }
    

    long long版本(大数据用)

    long long gcd(long long a, long long b)
    {
        while(b)
        {
            long long rem = a % b;
            a = b;
            b = rem;
        }
        return a;
    }
    

    LCM最小公倍数(C++14无内置,手写)

    公式:lcm(a,b) = a / gcd(a,b) * b,先除后乘防溢出!

    long long lcm(long long a, long long b)
    {
        return a / gcd(a,b) * b;
    }
    

    带上输入输出加速完整C++14模板

    #include <iostream>
    using namespace std;
    
    int gcd(int a, int b)
    {
        while(b)
        {
            int rem = a % b;
            a = b;
            b = rem;
        }
        return a;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int x,y;
        cin >> x >> y;
        cout << gcd(x,y) << '\n';
        return 0;
    }
    

    总结:C++14比赛,优先手写gcd,兼容性最强,不会踩编译器版本坑。

    • @ 2026-10-9 19:17:25

      __gcd(双下划线,旧版GCC内置函数)

      注意:两个下划线开头 __gcd(),不是C++17标准的std::gcd,是GCC扩展,信奥比赛常用!

      头文件

      #include <algorithm>
      

      示例代码

      #include <iostream>
      #include <algorithm> // __gcd
      using namespace std;
      
      int main(){
          int a = 24, b = 18;
          cout << __gcd(a,b) << endl; //输出6
          return 0;
      }
      

      ⚠️ 关键坑点(比赛必看)

      1. __gcd(a,b) 只支持非负数 如果传入负数,结果错误!需要先取绝对值:__gcd(abs(a),abs(b))
      2. __gcd(0,0) 未定义,会异常
      3. 这是GCC私有扩展,不是C++标准 MSVC编译器不支持!只有NOI、GESP用的GCC可以跑。
      4. 参数类型必须一致,不能一个int一个long long,否则报错。

      和 std::gcd 的对比

      函数 标准 头文件 备注
      __gcd GCC扩展 <algorithm> 比赛老代码常用,双下划线
      std::gcd C++17标准 <numeric> 跨编译器,单下划线,需要开C++17

      ✅ 保险手写版(推荐比赛万能写法,不受编译器限制)

      int gcd(int a,int b){
          while(b){
              int t=a%b;
              a=b;
              b=t;
          }
          return a;
      }
      

      配套最小公倍数

      lcm(a,b)=agcd(a,b)×blcm(a,b)=\frac{a}{gcd(a,b)} \times b

      先除后乘防止爆 long long!

      long long lcm(long long a,long long b){
          return a / gcd(a,b) * b;
      }
      
      • @ 2026-7-31 20:12:12

        GESP/信奥专用 辗转相除法(欧几里得算法)超全教程

        前言(竞赛必考说明)

        辗转相除法是 GESP 1-4级、CSP-J 入门组 核心必考算法,主要用于求解:两个数的最大公约数(GCD)、最小公倍数(LCM),是约分、分数运算、数论基础题的核心模板。

        本教程为信奥应试版本,只保留考场有用内容,提供可直接默写的满分模板、易错点、经典真题。

        一、算法核心原理(考场必背)

        1. 定义

        最大公约数:能够同时整除 a、b 的最大正整数,简写 GCD。

        2. 核心公式(欧几里得定理)

        gcd⁡(a,b)=gcd⁡(b, a mod b)\gcd(a,b) = \gcd(b,\ a\bmod b)

        3. 终止条件

        当 b = 0 时,当前的 a 就是最大公约数。

        4. 演算示例(考场理解)

        求 gcd(48,18): gcd(48,18) = gcd(18,12) gcd(18,12) = gcd(12,6) gcd(12,6) = gcd(6,0) b=0,结束,答案为 6

        二、最小公倍数公式(配套必考)

        已知最大公约数,可直接求最小公倍数 LCM:

        lcm(a,b)=agcd⁡(a,b)×b\text{lcm}(a,b) = \dfrac{a}{\gcd(a,b)} \times b

        💡 竞赛超级易错点:必须先除后乘! 禁止写 a*b/gcd,两数相乘极易爆 int 溢出,直接丢分。

        三、两套考场满分模板(直接默写)

        信奥考试只推荐两种写法:迭代版(稳定首选)、递归版(代码最短)

        模板1:迭代 while 版(GESP最推荐、不爆栈、万能)

        适用:所有GESP题目、数据量大、无递归深度限制

        <cstdlib> // abs函数
        using namespace std;
        
        // 最大公约数 GCD 万能模板
        int gcd(int a, int b)
        {
            a = abs(a);
            b = abs(b);
            while(b != 0)
            {
                int r = a % b;
                a = b;
                b = r;
            }
            return a;
        }
        
        // 最小公倍数 LCM 模板
        int lcm(int a, int b)
        {
            return a / gcd(a,b) * b;
        }
        
        int main()
        {
            int x,y;
            cin >> x >> y;
            cout< gcd(x,y)< endl;
            cout< lcm(x,y)< endl;
            return 0;
        }
        

        模板2:递归极简版(代码最短,适合快速做题)

        #include <iostream>
        #include <cstdlib>
        using namespace std;
        
        int gcd(int a,int b)
        {
            if(b == 0) return abs(a);
            return gcd(b, a % b);
        }
        
        int lcm(int a,int b)
        {
            return a / gcd(a,b) * b;
        }
        
        int main()
        {
            int a,b;
            cin >> a >> b;
        < gcd(a,b) << " " << lcm(a,b);
            return 0;
        }
        

        四、GESP 官方考点总结(必记)

        1. 自动适配大小数

        无需手动判断 a、b 大小! 例:gcd(18,48) 和 gcd(48,18) 结果完全一致,算法自动处理。

        2. 负数处理

        题目可能输入负数,必须加 abs(),否则答案错误。

        3. 特殊边界(填空/判断题高频)

        • gcd(x, 0) = |x|
        • gcd(0,0) 无意义,题目不会出现
        • 两个质数的 GCD 一定为 1

        4. 数据范围规范

        • GESP1-3级:int 足够使用
        • GESP4级/CSP-J 大数:将 int 改为 long long 即可

        五、进阶:long long 高精度模板(应对大数据)

        当题目数值超过 int 范围,使用此满分模板:

        <iostream>
        #include<cstdlib>
        using namespace std;
        
        typedef long long ll;
        
        ll gcd(ll a,ll b)
        {
            a = llabs(a);
            b = llabs(b);
            while(b)
            {
                ll r = a % b;
                a = b;
                b = r;
            }
            return a;
        }
        
        ll lcm(ll a,ll b)
        {
            return a / gcd(a,b) * b;
        }
        
        int main()
        {
            ll a,b;
            cin >> a >> b;
        < gcd(a< endl;
            return 0;
        }
        

        六、GESP 经典真题演练

        真题1:基础求值

        输入两个正整数 24、16,输出最大公约数和最小公倍数。 标准答案:GCD=8,LCM=48

        真题2:判断题考点

        使用辗转相除法计算 gcd(15,25),循环执行次数为?(答案:2次)

        真题3:应用题(分数约分)

        输入分子、分母,输出最简分数。 思路:求出GCD,分子分母同时除以GCD。

        // 最简分数代码
        int main()
        {
            int a,b;
            cin >> a >> b;
            int d = gcd(a,b< a< b/d;
            return 0;
        }
        

        七、考场终极避坑清单(扣分点全规避)

        • ❌ 错误:先乘后除 a*b/gcd → 极易溢出
        • ✅ 正确:先除后乘 a/gcd*b
        • ❌ 错误:不处理负数,输入负数直接WA
        • ❌ 错误:递归写复杂,导致逻辑出错
        • ✅ 应试首选:while 迭代模板,稳定零失误
        • 1