题意

给你一个同余方程 ，让你求最小正整数解，无解的话，输出-1

思路

同余方程可以等价于 （不知道为什么这边的加法失效了）,简单移项可以得到 ，那么我们就可以拓展欧几里得来求解了

注意事项

拓展欧几里得的解不一定是最小正整数解，我们需要转化下

代码

#include<bits/stdc++.h>

#define de(x) std::cout << #x << " = " << x << '\n';  
#define dd(x) std::cout << #x << " = " << x << ' ';  
#define qc std::ios_base::sync_with_stdio(0);std::cin.tie(0)
typedef long long ll;

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) return x = 1, y = 0, a;
    ll g = exgcd(b, a % b, x, y);
    std::tie(x, y) = std::make_tuple(y, x - a / b * y);
    return g;
}

ll qpow(ll a, ll b, ll m) {
    // if (b < 0) assert(0);
    ll ret = 1;
    while(b) {
        if (b & 1) ret = ret * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ret;
}

int get_phi(int x) {
    ll ret = 1;
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            ret *= (i - 1);
            x /= i;
            while(x % i == 0) {
                ret *= i;
                x /= i;
            }
        }
    }
    // de(x);
    if (x != 1) ret *= (x - 1);
    return ret;
}
int main() {
    qc;
    int t; std::cin >> t;
    while(t--) {
        int a, b; std::cin >> a >> b;
        ll x = -1, y = -1;
        ll g = exgcd(a, b, x, y);
        if (g != 1) std::cout << "-1" << '\n';
        else {
           if (a * x + b * y != g) assert(0);
           if (x) {
              if (x < 0) {
                  ll k = (-x + b - 1) / b;
                  if (-x == k * b) k++;
                  std::cout << x + k * b << '\n';
              } else {
                  ll k = x / b;
                  x -= k * b;
                  if (!x) std::cout << b << '\n';
                  else std::cout << x << '\n';
              }
           } else {
               std::cout << b << '\n';
           }
           // int phi_b = get_phi(b);
           // // de(phi_b);
           // std::cout << qpow(a, phi_b - 1, b) << '\n';
        }
    }
    return 0;
}