题解 | #【模板】同余方程#

【同余方程】 模板题，直接用exgcd就行了，上一场的青蛙的约会搞懂了，自然就会了。

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    return res;
}

int T, a, b, x, y, d;
signed main() {
    cin >> T;
    while (T--) {
        cin >> a >> b;
        d = exgcd(a, b, x, y);
        if (d != 1) {
            cout << -1 << "\n";
        } else {
            cout << (x % b + b) % b << "\n";
        }
    }

    return 0;
}