Acwing 扩展欧几里得算法

1.扩展欧几里得算法

回忆：求最大公约数中学过欧几里得算法（辗转相除法）：gcd(a,b) == gcd(b, a % b)；
裴蜀定理：对于任意正整数a,b,那么一定存在非零整数x,y,使得ax+by=gcd(a,b);
扩展欧几里得算法：就是求解上面裴蜀定理中a和b的系数x,y;具体怎么求？

• 首先若b=0，那么显然gcd(a,0)=a,则可得x=1，y=0；
• 若a,b都不为0，结合欧几里得算法gcd(a,b) == gcd(b, a % b)，那么ax+by=gcd(a,b)===>b*x+(a%b)*y=gcd(a,b)，但在递归的过程中a的系数由x变为y，b的系数由y变为x，所以在递归过程的传入参数时因调换x和y的位置，变为b*y+(a%b)*x=gcd(a,b)，下面的代码会体现；
• 设gcd(a,b)=d，那么继续推理得到
• 
  即可求出系数，注意x和y可能不是唯一的。

Acwing 877.扩展欧几里得算法

具体实现代码（详解版）：

#include <iostream>

using namespace std;

// 扩展欧几里得算法函数
int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1;  // 基本情况：如果 b == 0，x 为 1
        y = 0;  // y 为 0，因为 a * 1 + b * 0 = a
        return a; // 返回 gcd(a, b)
    }
    int d = exgcd(b, a % b, y, x); // 递归调用
    y -= (a / b) * x; // 使用之前的 x 更新 y
    return d; // 返回 gcd
}

int main() {
    int n;
    cin >> n; 
    while (n--) {
        int a, b, x, y;
        cin >> a >> b; 
        exgcd(a, b, x, y); // 调用扩展欧几里得算法
        cout << x << ' ' << y << endl; // 输出系数 x 和 y
    }
    return 0; 
}

下面给出一个扩展欧几里得算法的应用。

2.Acwing 878.线性同余方程

实现思路：对于(a*x) mod m=b，求解x。

• 恒等变形可以得a*x=m*y'+b=>a*x-m*y'=b=>a*x+m*y=b，此时就形似扩展欧几里得算法，则由裴蜀定理可知a*x+m*y=gcd(a,m)必然有解，假如b是gcd(a,m)的倍数，即必然存在这样的x和y，使所求等式有解，只需等式两边扩大相应的倍数即可。此时x=x*(b/gcd(a,m))
• 这里最后**x*(b/gcd(a,m))%m**是为了得到最小的解，因为x的通解有无数个，防止超出int范围，就取一个最小的

具体实现代码（详解版）：

#include <iostream>

using namespace std;
typedef long long LL; // 定义 LL 为 long long 类型

// 扩展欧几里得算法函数
int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1;  // 基本情况：如果 b == 0，x 为 1
        y = 0;  // y 为 0，因为 a * 1 + b * 0 = a
        return a; // 返回 gcd(a, b)
    }
    int d = exgcd(b, a % b, y, x); // 递归调用
    y -= (a / b) * x; // 使用之前的 x 更新 y
    return d; // 返回 gcd
}

int main() {
    int n;
    cin >> n; 
    while (n--) {
        int a, b, m, x, y;
        cin >> a >> b >> m; 
        int d = exgcd(a, m, x, y); // 调用扩展欧几里得算法
        if (b % d == 0) { // 如果 b 是 d 的倍数
            cout << (LL)x * (b / d) % m << endl; // 输出最小解
        } else {
            puts("impossible"); // 输出 "impossible"
        }
    }
    return 0; 
}

3.中国剩余定理

$$\begin{gathered} x有k个两两互质的数m_1、m_2、\dots 、m_k \\ 给定线性同余方程组x\equiv a_1(mod{m}_1)、x\equiv a_2(mod{m}_2)、\dots 、x\equiv a_k(mod{m}_k) \\ 求x解法： \\ 令M=m_1\times m_2\times \cdots \times m_k，M_i=\frac{M}{m_i}，用M_i^{-1}表示M_i模的逆 \\ (求M_i^{-1}：M_i\times M_i^{-1}\equiv 1(mod{m}_i)，实质就是用扩展欧几里得求一个特殊的线性同余方程:a\times x\equiv 1(modm)) \\ 则x=a_1\times M_1\times M_1^{-1}+a_2\times M_2\times M_2^{-1}+\cdots +a_k\times M_k\times M_k^{-1} \\ 可以验证x为该线性同余方程组的解（略） \end{gathered}$$

Acwing 204.表达整数的奇怪方式

求解推导：
公式
$$\begin{gathered} 1.对于两个式子，考虑将其合并： \\ x\equiv m_1(\%a_1) \\ x\equiv m_2(\%a_2) \\ 则有：x=k_1\ast a_1+m_1,x=k_2\ast a_2+m_2, \\ 进一步联立上面两式：k_1\ast a_1+m_1=k_2\ast a_2+m_2==>{\mathbf{k}}_1\ast {\mathbf{a}}_1+{\mathbf{k}}_2\ast (-{\mathbf{a}}_2)={\mathbf{m}}_2-{\mathbf{m}}_1...① \\ 也就是我们要找到一个最小的k_1,k_2，使得等式成立(因为要求x最小，而a和m都是正数) \\ 2.对a_1和a_2使用扩展欧几里得得到最小公约数d=gcd(a_1,-a_2) \\ 即{\mathbf{k}}_1\ast {\mathbf{a}}_1+{\mathbf{k}}_2\ast {\mathbf{a}}_2=\mathbf{d}=\mathbf{gcd}({\mathbf{a}}_1,-{\mathbf{a}}_2)...② \\ 此时对于①和②式就出现了之前求线性同余方程的情况，即m_2-m_1是d的倍数时(d|m_2-m_1)方程有解 \\ ②式两边乘\frac{m_2-m_1}{d}就转化为①式 \\ 即{\mathbf{k}}_1\ast {\mathbf{a}}_1\ast \frac{{\mathbf{m}}_2-{\mathbf{m}}_1}{\mathbf{d}}+{\mathbf{k}}_2\ast {\mathbf{a}}_2\ast \frac{{\mathbf{m}}_2-{\mathbf{m}}_1}{\mathbf{d}}={\mathbf{m}}_2-{\mathbf{m}}_1 \\ 3.有解的情况下得到一组解: \\ {\mathbf{k}}_1={\mathbf{k}}_1\ast \frac{{\mathbf{m}}_2-{\mathbf{m}}_1}{\mathbf{d}},{\mathbf{k}}_2={\mathbf{k}}_2\ast \frac{{\mathbf{m}}_2-{\mathbf{m}}_1}{\mathbf{d}},注意这里k就表示特解 \\ 4.找最小正整数解：模尽倍数后，剩下的余数就是最小正整数解 \\ {k}_1=k_1\%abs(\frac{a_2}{d}),k_2=k_2\%abs(\frac{a_1}{d}) \\ 5.找满足方程的所有解 \\ 将一组方程的解带回方程：k_1\ast a_1+k_2\ast a_2=c \\ 等式左边加减\frac{a_1\ast a_2}{d},方程右边不变，可得： \\ {k}_1\ast a_1+k_2\ast a_2+a_1\ast \frac{a_2}{d}-a_2\ast \frac{a_1}{d}=(k_1+\frac{a_2}{d})\ast a_1+(k_2-\frac{a_1}{d})\ast a_2=c \\ 于是得到所有解集：{\mathbf{k}}_1={\mathbf{k}}_1+\frac{{\mathbf{a}}_2}{\mathbf{d}}\ast \mathbf{k},{\mathbf{k}}_2={\mathbf{k}}_2-\frac{{\mathbf{a}}_1}{\mathbf{d}}\ast \mathbf{k} \\ 6.再代入k_1,k_2得新的x为：x=(k_1+\frac{a_2}{d}\ast k)\ast a_1+m_1 \\ =k_1\ast a_1+m_1+\frac{a_1\ast a_2}{d}\ast k \\ 令新的a_1^{{}^{\prime }}=\frac{a_1\ast a_2}{d},新的m_1^{{}^{\prime }}=k_1\ast a_1+m_1 \\ 那么x=a_1^{{}^{\prime }}\ast k+m_1^{{}^{\prime }},这时就又回到了第一步，至此完成两个式子的合并, \\ 后续再来一个a_3,m_3同理继续合并，n个式子进行n-1次合并得到最终式 \end{gathered}$$

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

// 扩展欧几里得算法函数
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x); // 递归调用
    y -= a / b * x; // 更新 y
    return d; // 返回 gcd(a, b)
}

int main() {
    int n;
    cin >> n; // 读取方程的数量
    bool has_answer = true; // 假设有解
    LL a1, m1;
    cin >> a1 >> m1; // 读取第一个方程的系数 a1 和余数 m1
    
    // 迭代处理剩余的方程
    for (int i = 0; i < n - 1; i++) {
        LL a2, m2;
        cin >> a2 >> m2; // 读取下一个方程的系数 a2 和余数 m2
        
        LL k1, k2;
        LL d = exgcd(a1, a2, k1, k2); // 计算 a1 和 a2 的 gcd
        
        // 如果 m2 - m1 不能被 gcd(a1, a2) 整除，则无解
        if ((m2 - m1) % d) {
            has_answer = false;
            break;
        }
        
        // 更新 k1，找到合适的 k1
        k1 *= (m2 - m1) / d;
        LL t = a2 / d;
        k1 = (k1 % t + t) % t; // 使 k1 是模 t 的正数解
        
        // 更新 m1 和 a1
        m1 = a1 * k1 + m1;
        a1 = abs(a1 / d * a2); // 更新 a1 为最小公倍数
    }
    
    // 输出结果
    if (has_answer) {
        cout << (m1 % a1 + a1) % a1 << endl; // 输出最小非负解
    } else {
        puts("-1"); // 无解
    }
    
    return 0;
}

以上就是扩展欧几里得算法及其应用，关键是掌握欧几里得算法，应用可能推导较难，见机行事~