AcWing 878. 线性同余方程

一、理解与感悟

1、线性同余方程【扩展欧几里得算法的一个典型应用】

(axequiv 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;)
...
不会产生(3)这个余数，所以，无解。

(4xequiv 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=2),第二个解是(7)。
这两个解之间差了一个(5)，即(2+5=7)，每加一个(5)，都可以得到一个解。比如 (7+5=12)也是一个解。

2、为什么线性同余方程可以使用欧几里得算法来求解呢？

(1) (a∗xequiv 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) ,这就是一个标准的二元一次方程。

(2) 根据贝祖定理，上述等式有解当且仅当 (gcd(a,m)|b)，也就是(b)是(gcd(a,m))的整数倍，有解；
如果(b)不是(gcd(a,m))的整数倍，无解，输出(impossible)。

(3) 用扩展欧几里得求出一组特解 (x_0),(y_0), 使得 (a∗x_0+m∗y_0=gcd(a,m))。

(4)对比两个方程：扩展欧几里得公式和线性同余方程两个东东

(a*x + m*y = b)

(a∗x_0+m∗y_0=gcd(a,m))

两个方程的左右两边，左边的系数是一样的(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))是一个整数。

( herefore 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() {
    //优化输入
    ios::sync_with_stdio(false);
    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
", (LL) b / d * x % m);
    }
    return 0;
}