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

重点
1. 线性同余方程如何转化，ax = b(mod) => ax - my = b
2. 有解的条件：求出的d是b的倍数
3. 裴叔定理，ax + by = d，中xy为整数，则d一定是gcd(a,b)的倍数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

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


    return 0;
}