##[$AcWing$ $878$. 线性同余方程](https://www.acwing.com/problem/content/description/880/)

### 一、题目描述
给定 $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$

**输入样例：**
```cpp {.line-numbers}
2
2 3 6
4 3 5
```

**输出样例：**
```cpp {.line-numbers}
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$

---

...
<font color='red' size=4><b>余数开始循环了，一直都是$2,4,0$...</b></font>

不会产生$3$这个余数，所以，无解。

**再来一个栗子：**

$4x\equiv\ 3 (mod\ 5)$    

$x=1,4x=4, 4\%5 =4$ 
<font color='red'>$x=2,4x=8, 8\%5 =3$</font>
$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$
<font color='red'>$x=7,4x=28, 28\%5 =3$</font>
$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}
a*x + m*y = 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$.即：

```c++
(LL) b / d * x % m
```

### 三、实现代码
```cpp {.line-numbers}
#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;
}

```