【算法学习笔记】35：扩展欧几里得算法求解线性同余方程

线性同余方程问题

线程同余方程问题是指$ax\equiv b(modm)$，给定$a$、$b$和$m$，找到一个整数$x$使得该方程成立，即使得$axmodm=b$，随便返回任何一个解都可以。

例如$4x\equiv 3(mod5)$，那么$x$的一个可能的解可以是$2$。

接下来用扩展欧几里得算法尝试构造这个解。从$ax\equiv b(modm)$可知，一定存在一个$y$使得：
$$a\cdot x=m\cdot y+b$$

也就是说，因为$ax$模$m$的余数是$b$，所以$ax$一定可以表示成$m$的整数$y$倍再加上一个$b$。也就是：
$$ax-my=b$$

令$y^{\prime }=y$，那么就是：
$$ax+m{y}^{\prime }=b$$

因此原线性同余方程问题求$x$有解，等价于这个方程求$x$和$y^{\prime }$有解。而根据扩展欧几里得算法里所讨论的，$a$是$gcd(a,m)$的倍数，$m$也是$gcd(a,m)$的倍数，所以它们拼到一起也必须是$gcd(a,m)$的倍数。

因此，这个方程有解的充要条件是$b$必须是$gcd(a,m)$的倍数，也即$gcd(a,m)|b$ 。

例题：AcWing 878. 线性同余方程

这题最终结果要限制在int范围内，因为$m$也是在int范围内的，并且：
$$\begin{gathered} ax+my=b \\ \iff a(km+r)+my=b \\ \iff ar+m(ak+y)=b \end{gathered}$$
也就是说，把系数$x$变成$r=xmodm$时，另一个系数只要从$y$变成$ak+y$就可以了，其中$k=\lfloor \frac{x}{m}\rfloor$。

所以可以直接把结果$x$模$m$，一定也是一个合法的解，并且满足在int范围内的要求。

#include <iostream>

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);
    // d = b * y + (a % b) * x = b * y + (a - a / b * b) * x
    //   = a * x + b * (y - a / b * x)
    y -= a / b * x;
    return d;
}

int main() {
    int t; cin >> t;
    
    while (t -- ) {
        int a, b, m; cin >> a >> b >> m;
        // ax % m = b, ax + my' = b, iff gcd(a, m) = d | b
        int x, y;
        int d = exgcd(a, m, x, y);
        if (b % d) puts("impossible");
        else cout << (LL)x * (b / d) % m << endl;
    }
    
    return 0;
}

原文地址：https://blog.csdn.net/SHU15121856/article/details/145270148

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！