3.9 KiB
一、题目描述
给定 n 组数据 a_i,b_i,m_i，对于每组数求出一个 x_i，使其满足 a_i×x_i≡b_i(mod \ m_i)，如果无解则输出 impossible。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组数据 a_i,b_i,m_i。
输出格式
输出共 n 行，每组数据输出一个整数表示一个满足条件的 x_i，如果无解则输出 impossible。
每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在 int 范围之内。
数据范围
1≤n≤10^5,1≤a_i,b_i,mi≤2×10^9
输入样例：
2
2 3 6
4 3 5
输出样例：
impossible
-3
二、线性同余方程
【扩展欧几里得算法的一个典型应用】
ax\equiv\ b(mod\ m)
举个栗子：
2x \equiv 3 (mod\ 6)
x=1,2x=2,2\%6=2
x=2,2x=4,4\%6=4
x=3,2x=6,6\%6=0
x=4,2x=8,8\%6=2
x=5,2x=10,10\%6=4
x=6,2x=12,12\%6=0
...
余数开始循环了，一直都是2,4,0...
不会产生3这个余数，所以，无解。
再来一个栗子：
4x\equiv\ 3 (mod\ 5)
x=1,4x=4, 4\%5 =4
x=2,4x=8, 8\%5 =3
x=3,4x=12, 12\%5 =2
x=4,4x=16, 16\%5 =1
x=5,4x=20, 20\%5 =0
x=6,4x=24, 24\%5 =4
x=7,4x=28, 28\%5 =3
x=8,4x=32, 32\%5 =2
x=9,4x=36, 36\%5 =1
x=10,4x=40, 40\%5 =0
....
所以有解，其它第一个解是 x=2,第二个解是7。
这两个解之间差了一个5，即2+5=7，每加一个5，都可以得到一个解。比如 7+5=12也是一个解。
2、为什么线性同余方程可以使用欧几里得算法来求解呢？
a∗x\equiv b (mod\ m)表示意义 是(a*x) \% m=b,从而(a∗x−b)\%m=0。
假设是y_1倍，因此线性同余方程转化为 a∗x-b=m∗y_1 ， 移项： a*x-m*y_1=b。令 -y_1=y ,则: a * x + m * y = b ,这就是一个标准的二元一次方程。
-
根据贝祖定理，上述等式有解当且仅当
gcd(a,m)|b，也就是b是gcd(a,m)的整数倍，有解； 如果b不是gcd(a,m)的整数倍，无解，输出impossible -
用扩展欧几里得求出一组特解
x_0,y_0, 使得a∗x_0+m∗y_0=gcd(a,m)。 -
对比两个方程：扩展欧几里得公式和线性同余方程两个东东
$ \large \left{\begin{matrix} ax + my = b & \ a∗x_0+m∗y_0=gcd(a,m) & \end{matrix}\right. $
两个方程的左右两边，左边的系数是一样的a,m,右边的常数不一样，一个是b,另一个是gcd(a,m)，我们刚才上面讨论过，b必须是gcd(a,m)的整数倍，方程才有解，也就是说，现在b一定是gcd(a,m)的整数倍！
设 d=gcd(a,m),那么b=t*d,其中t=b/gcd(a,m)是一个整数。
\therefore x=b/gcd(a,m) * x_0,
因为害怕在乘法运算过程中，造成爆int,所以，出发前对b进行了转long\ long操作，以保证不爆int.同时，因为是同余方程，如果取得的值大于m,还需要模一下m.即：
(LL) b / d * x % m
三、实现代码
#include <bits/stdc++.h>
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
printf("%d\n", (LL)b / d * x % m);
}
return 0;
}