[数论+模板] 裴蜀定理及扩展欧几里得算法模板(模板)

文章目录

1. 裴蜀定理与扩展欧几里得定理的证明

也可参考大佬题解

2. 扩展欧几里得算法+模板

877. 扩展欧几里得算法

重点： 扩展欧几里得算法

有关于递归的部分，递归结束之后应该得到了 a 和 b 的最大公约数。在此关于递归函数内部传参有两种写法

• exgcd(b, a % b, x1, y1); 这个完全以原问题出发，推导 gcd(a, b) = gcd(b, a % b) 这个式子的拓展欧几里得展开式，最后系数对应相等即可。x = y1, y = x1 - a / b * y1; 将递归中的系数返回给 x 和 y 这两个输出型参数。
• exgcd(b, a % b, y, x); 这个巧妙的将 y 和 x 位置互换，就自然而然的完成了 x = y1 这个操作，代码少了一行，也不需要再创建变量了。很是巧妙！

具体公式推导可参考大佬题解

模板代码：

#include <iostream>
#include <algorithm>

using namespace std;

// 易理解
int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    
    int x1, y1, d;
    d = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    
    return d;
}

// 更加简洁
int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    
    int d = exgcd(b, a % b, y, x);      // 递归求解到gcd(a, b)
    y -= a / b * x;
    
    return d;
}

int main() {
    int n;
    cin >> n;
    
    while (n --) {
        int a, b;
        cin >> a >> b;
        
        int x, y;
        exgcd(a, b, x, y);
        
        cout << x << ' ' << y << endl;
    }
    
    return 0;
}

3. 快速幂求逆元+模板

878. 线性同余方程

重点： 扩展欧几里得原理

思路：

• 很经典，利用扩展欧几里得原理求解线性同余方程组
• 问题可以转化为 ax = my + b，则 ax - my = b
• 当 gcd(a, m) | b 就可以通过拓展欧几里得原理计算得到 a 和 m 的系数
• 当 gcd(a, m) 不能整除 b 时，则无解

模板代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    int n;
    cin >> n;
    
    while (n --) {
        int a, b, m;
        cin >> a >> b >> m;
        
        int x, y;
        int d = exgcd(a, m, x, y);
        if (b % d) puts("impossible");
        else cout << (LL)b / d * x % m << endl;
    }
    
    return 0;
}