欧几里得算法

简介

欧几里得算法是常用的求两数公因数的算法之一。它又被称为辗转相除法。它通过递归解决这个问题。由于它的简单和高效，它在OI领域中被广泛运用。

说明

欧几里得算法的计算过程如下。

本算法基于一个定理：两个整数的最大公因数等于其中较小的那个数和两数相除余数的最大公因数。我们用gcd(a, b)表示两个整数a、b的最大公因数。则该定理可以表示为gcd(a, b) = gcd(b, a%b) (a > b)。

算法的过程即是递归调用上述函数，当b=0时a即是原a和b的gcd。

代码

int gcd(int a, int b) {
    if(b == 0) return a;
    if(b > a) swap(a, b);
    return gcd(b, a % b); // 递归求解
}

证明

本算法的证明非常复杂，暂时不予提供。

可以参考以下文章。

数学 – 如何证明这种欧几里得(最大公约数)算法的正确性？ – SegmentFault

例题及解析

待补充

扩展欧几里得算法

简介

扩展欧几里得算法是用于解决形如ax+by=d（a, b, d是整常数，x, y是整数）的不定方程的求整数解的问题的一种方法。它同样因为易于理解以及简单而被广泛使用。它的使用并不是广泛的，它需要先满足ax+by=gcd(a, b)=d这一条件（贝祖等式）才能够用于求整数解。

说明

扩展欧几里得算法的证明较为繁琐，我们将其分为几步证明。

①根据欧几里得算法中的结论进行代换。
这里指的结论是gcd(a, b)=gcd(b,  a%b)。看到原式ax+by=gcd(a, b)。将a换为b，b换为a%b，得到右式bx+(a%b)y=gcd(b, a%b)。再由上述结论得到bx+(a%b)y=gcd(a, b)。

②探究原式的解与推出方程的解的关系。
我们设推出方程有解x₂, y₂，则有bx₂+(a%b)y₂=gcd(a, b)成立。实际上有a%b=a-(a/b)*b（注：此处a/b向下取整），代入整理得到式ay₂+b(x₂-(a/b)*y₂)=gcd(a, b)。设原方程有解x₁, y₁，则有ax₁+by₁=gcd(a, b)成立。联立上述式子，解得x₁=y₂, y₁=x₂-(a/b)*y₂。

③反推求得x₁, y₁。
我们知道在欧几里得算法的时候通过递归将gcd(a, b) = gcd(b, a%b)进行到底，我们完全可以在这个过程中顺便算出x₁, y₁。试令b=0，可以发现gcd(a, b)=a=ax₁+by₁，则此时有解x₁=1, y₁=0。将此过程中下一层递归的解作为本层的x₂, y₂，便可解得最初形式的方程的解。

④得到方程的通解。
对于已得到的一组解x₁, y₁，不妨设x=x₁+kt，代入方程中解得y=y₁-ak/bt。此时，我们要保证ak/b是整数，自然会想到如何约去这个b。不妨令k=b/gcd(a, b)，这样x=x₁+bt/gcd(a, b)，y=y₁+at/gcd(a, b)便是原方程的通解公式。

代码

int exgcd(int a, int b, int &x, int &y) {
    if(b == 0) {
        x = 1; // 设置b=0时的特殊解 
        y = 0;
        return a;
    }
    int ans = exgcd(b, a % b, x, y);
    int t = x; // 将x2, y2换算成x1, y1
    x = y;
    y = t - a / b * y;
    return ans;
}

应用：求逆元

逆元是指使ax≡1 (mod m)成立的x值。可以应用扩展欧几里得算法求得该值，具体做法如下。

①化简整理原式。
原式等价于ax%b=1，即(ax-1)/b=y（y为整数）。由于已知b是正整数，消去得ax-by=1。由于认为gcd(a, -b)=gcd(a, b)，因此该式等效于ax+by=1。

②应用扩欧求解。

③求最小正整数解。
我们找到x的通式为x=x₁+bt/gcd(a, b)，由于此处gcd(a, b)为1，可化简为x=x₁+bt。要靠近数轴原点，需要进行x₁%b操作。然而我们知道取模后可能得到一个负数，则加上负数判断并对负数加b即可解决问题。

代码如下。

int invele(int a, int m) {
    int x, y;
    exgcd(a, m, x, y);
    if(m < 0) m = -m;
    int ans = x % m;
    if(ans <= 0) ans += m;
    return ans;
}

参考资料

1. 扩展欧几里德算法详解 - 蛤蛤~ - CSDN博客

2. 扩展欧几里得算法(extgcd) - 殇雪 - 博客园

3. 扩展欧几里得算法 | Acm之家

4. 扩展欧几里得算法及其应用 - Just for you - CSDN博客

5. 逆元详解 - ACdreamer - CSDN博客

例题：同余方程 洛谷P1082

3 10

7

#include <cstdio>
typedef long long ll;

ll ex_gcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll ans = ex_gcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return ans;
} 

int main() {
    ll a, b, x, y;
    scanf("%lld%lld", &a, &b);
    ex_gcd(a, b, x, y);
    x %= b;
    if(x < 0) x += b; 
    printf("%lld", x);
    return 0;
}