---
title: "欧几里得算法（辗转相除）"
created: 2025-11-28
tags:
  - 算法
---

# 欧几里得算法（辗转相除）

## 题目 [最大公约数](https://www.acwing.com/problem/content/874/)

![[image-87b53a2b.png]]

## 思路分析

**什么是最大公约数**

最大公约数指两个或多个整数共有约数中最大的一个

也称最大公因数、最大公因子，a， b的最大公约数记为（a，b）

同样的，a，b，c的最大 公约数记为（a，b，c）

多个 整数的最大公约数也有同样的记号

求最大公约数有多种 方法 常见的有 质因数分解法 短除法 辗转相除法 更相减损法

**辗转相减法求最大公约数**

用(a，b)表示a和b的最大公因数：有结论(a，b)=(a，ka+b)，其中a、b、k都为自然数。

也就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数，其公约数不变，比如(4，6)=(4+6，6)=(4，6+2×4)=2.

要证明这个原理很容易：如果p是a和ka+b的公约数，p整除a，也能整除ka+b.那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的.

基于上面的原理，就能实现我们的迭代相减法：

(78，14)=(64，14)=(50，14)=(36，14)=(22，14)=(8，14)=(8，6)=(2，6)=(2，4)=(2，2)=(0，2)=2

基本上思路就是大数减去小数，一直减到能算出来为止，在作为练习的时候，往往进行到某一步就已经可以看出得值

**辗转相减到辗转相除**

迭代相减法简单，不过步数比较多，实际上我们可以看到，在上面的过程中，由(78，14)到(8，14)完全可以一步到位，因为(78，14)=(14×5+8，14)=(8，14)，由此就诞生出我们的辗转相除法.

即：(a， b) = (a % b， b) = （b, a %b）

相当于每一步都把数字进行缩小 等式右边就是每一步对应的缩小结果

对（a， b）连续使用辗转相除 直到小括号内右边数字为0 小括号内左边的数就是两数最大公约数

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

int main()

{

    int T;cin>>T;

    while(T--){

        int a,b;

        cin>>a>>b;

        while(b){

            int c=a%b;

            a=b;

            b=c;

        }

        cout<<a<<endl;

    }

    return 0;

}
```

可进行封装

```cpp
#include<bits/stdc++.h>

using namespace std;

int gcd(int a,int b){

    return b ? gcd(b, a % b) : a;

}

int main()

{

    int T;cin>>T;

    while(T--){

        int a,b;

        cin>>a>>b;

        cout<<gcd(a,b)<<endl;

    }

    return 0;

}
```

库函数\_gcd

```cpp
#include<bits/stdc++.h>

using namespace std;

int main()

{

    int T;cin>>T;

    while(T--){

        int a,b;

        cin>>a>>b;

        cout<<__gcd(a,b)<<endl;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[樱花|樱花]] 🏠 [[00-刷题理模型]] ➡️ [[等差数列|等差数列]]