[数据结构与算法]acwing 878 线性同余方程 2022/03/11

这里的d是最大公约数，如果要变成是b的话（原式相当于ax+my=b）只需要乘 b / d 就可

所以最后x乘以b / d

#include<bits/stdc++.h>
using namespace std;
int n, x, y;
using LL = long long ;
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int z = x;
    x = y;
    y = z - a / b * y;
    return d;
}

int main()
{
    cin >> n;
    while (n --)
    {
        int a, b, m;
        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;
        }
    }
    return 0;
}