线性同余方程
给定$n$组数据$a_i,b_i,m_i$,对于每组数求出一个$x_i$,使其满足$a_i \times x_i≡b_i \pmod m_i$
经过变化后可以得出:$a_i \times x_i -m_i \times y_i = b_i$
$$
\Rightarrow a_i \times x_i +m_i \times y_i = b_i
$$
所以说,就可以使用扩展欧几里得算法求出$x_i$的值,然后判断该等式方程是否存在解
该方程式存在解的充分必要条件是:$b$是$a$和$m$的最大公约数$d$的倍数
那么,我们最后使用扩展欧几里得算法所求出的结果$x$是基于$a$和$m$最大公约数的一个结果,想要求出和$b$相关的结果,需要将$x$扩大$b \div d$倍
$$
x = x \times b \div d \pmod m
$$
#include <iostream>
using namespace std;
int n;
typedef long long LL;
int exgcd(int a,int b,int& x,int& y) {
if(!b) {
x = 1, y = 0;
return a;
}
int x1,y1;
int ret = exgcd(b,a%b,x1,y1);
x = y1;
y = x1 - a / b * y1;
return ret;
}
int main() {
cin >> n;
while(n --) {
int a,b,m,x,y;
cin >> a >> b >> m;
int d = exgcd(a,m,x,y);
if(b % d) puts("impossible");
else {
x = (LL)x * b / d % m;
cout << x << endl;
}
}
}