[Acwing] 878. 线性同余方程

题意

求出一个 x i x_i xi​满足 a i ∗ x i ≡ b i ( m o m i ) a_i*x_i\equiv b_i(mo m_i) ai​∗xi​≡bi​(momi​)

思路

( m ∣ x m|x m∣x表示 m m m是 x x x的因子,或者 x x x能被 m m m整除)

首先什么是同余 ?

设整数 m ≠ 0 m\neq0 m​=0

若 m ∣ ( a − b ) m|(a-b) m∣(a−b),称 m m m位模数, a a a同余 b b b模 m m m, b b b是 a a a对模 m m m的剩余记作 a ≡ b ( m o d   m ) a\equiv b(mod\ m) a≡b(mod m)

则我们可以知道 a − b a-b a−b是 m m m的倍数,因此上面的式子可以化为 a ∗ x + y ∗ m = b \begin{aligned} &a*x+y*m=b\\ \end{aligned} ​a∗x+y∗m=b​

但是显然这里并不能使用 扩 展 欧 几 里 得 扩展欧几里得 扩展欧几里得

因为扩展欧几里得需要满足 a ∗ x + y ∗ m = g c d ( a , m ) \begin{aligned} &a*x+y*m=gcd(a,m)\\ \end{aligned} ​a∗x+y∗m=gcd(a,m)​

那么上面那个定理什么时候有解呢 ?

    a x + b y = c 设 d = g c d ( a , b )         d ∣ a , d ∣ b     d ∣ ( a x ) , d ∣ ( b y ) c = m ∗ d = m ∗ g c d ( a , b ) \begin{aligned} &\ \ \ ax+by=c\\ &设d=gcd(a,b)\\ &\ \ \ \ \ \ \ d|a,d|b\\ &\ \ \ d|(ax),d|(by)\\ &c=m*d=m*gcd(a,b) \end{aligned} ​   ax+by=c设d=gcd(a,b)       d∣a,d∣b   d∣(ax),d∣(by)c=m∗d=m∗gcd(a,b)​ 则显然 c c c是 g c d ( a , b ) gcd(a,b) gcd(a,b)的时候有解,这就是贝祖定理

因此我们又回去考虑 a ∗ x + y ∗ m = b \begin{aligned} &a*x+y*m=b\\ \end{aligned} ​a∗x+y∗m=b​

显然当 g c d ( a , m ) ∣ b gcd(a,m)|b gcd(a,m)∣b的时候有解

因此我们不妨先用扩展欧几里得求解出 a ∗ x 0 + y 0 ∗ m = g c d ( a , m ) \begin{aligned} &a*x_0+y_0*m=gcd(a,m)\\ \end{aligned} ​a∗x0​+y0​∗m=gcd(a,m)​

然后我们将式子左右两边同时乘上 b g c d ( a , m ) \frac{b}{gcd(a,m)} gcd(a,m)b​ ( a ∗ x 0 + y 0 ∗ m ) ∗ b g c d ( a , m ) = g c d ( a , m ) ∗ b g c d ( a , m ) a ∗ x 0 ∗ b g c d ( a , m ) + y 0 ∗ b g c d ( a , m ) = b \begin{aligned} &(a*x_0+y_0*m)*\frac{b}{gcd(a,m)}=gcd(a,m)*\frac{b}{gcd(a,m)}\\ &a*x_0*\frac{b}{gcd(a,m)}+y_0*\frac{b}{gcd(a,m)}=b \end{aligned} ​(a∗x0​+y0​∗m)∗gcd(a,m)b​=gcd(a,m)∗gcd(a,m)b​a∗x0​∗gcd(a,m)b​+y0​∗gcd(a,m)b​=b​

因此最后对于上面由扩展欧几里得求出的 x 0 x_0 x0​ 可以用来推导出所求式的 x x x

x = x 0 ∗ g c d ( a , m ) / b % m x = x_0*gcd(a,m)/b\%m x=x0​∗gcd(a,m)/b%m

Code :

#include 
#include 

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;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b, m;
        scanf("%d%d%d", &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;
}