题目链接

题意：求出一个x，使其满足 a*x ≡ b (mod m)， 等价于

求一个x, 满足 ax + my = b
而ax + my 的值一定是gcd(a, m)的倍数，所以当b 是 gcd(a, m)的倍数时有解
所以可以用exgcd求出 ax + my = gcd(a, m)的解x, 此时等式两边同时乘以b/gcd即可

下面这段代码才是精华

    int x, y, d = exgcd(a, m, x, y);
    if (b % d) puts("impossible");
    else printf("%d\n", (long long)x * (b / d) % m);
    /*(b / d)是一定是整数，转化为long long 避免损失精度。
    同时若x 满足ax ≡ b (mod m),则x%m也满足
    */

#include <iostream>
using namespace std;

int n, a, b, m;

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(){
    cin >> n;
    while (n --){
        scanf("%d%d%d", &a, &b, &m);
        int x, y, d = exgcd(a, m, x, y);
        if (b % d) puts("impossible");
        else printf("%d\n", (long long)x * (b / d) % m);
    }

    return 0;
}