【算法学习笔记】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 | bint x, y;int d = exgcd(a, m, x, y);if (b % d) puts("impossible");else cout << (LL)x * (b / d) % m << endl;}return 0;
}