扩展欧几里得算法求线性同余方程

本节需要前置知识扩展欧几里得算法，不了解的可以先看我的上一篇博文
裴蜀定理与扩展欧几里得算法

先介绍同余方程

ax\equiv b(mod \quad m)

该方程中，x是未知数，其余为已知，含义是求x，使得

ax \quad mod \quad m =b

该方程可以无解，或者有多解

上式不难写成

ax = my+b,y\in \mathbb{Z} ①

观察可以发现形式非常像扩展欧几里得算法中所求的方程

ax+by=gcd(a,b)②

将①式移项整理成和②相同的形式

ax + my'=b,y'=-y

由上节可知，该方程有解的充要条件是

gcd(a,b) \mid b

所以当该条件成立时，题目所求的x是方程中x扩大b/d倍的数，而不成立就直接输出imposs

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

//ax+by=gcd
LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
    {
        x = 1; y = 0;
        return a;
    }
    LL res = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        LL a, b, m;
        scanf("%lld %lld %lld",&a, &b, &m);
        LL x, y;
        LL d = exgcd(a, m, x, y);
        if (b % d)
            puts("impossible");
        else
            printf("%lld\n", (long long) (x * b / d) % m);
    }
    return 0;
}