题解

#include<bits/stdc++.h>
typedef __int128 iint;
using namespace std;

iint m;
iint gcd(iint a, iint b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
iint calc(iint h, iint d, iint k) { //h : 还剩的点数, d : 已经有解的点数
    if (h <= 0) return 0;
    iint g = gcd(m, k), k0 = k / g, m0 = m / g;
    if (g == 1) return 0; //无法进行任何合并
    if (h <= k0) return 0; //无法进行任何合并
    d *= m0;
    return h - k0 + calc(k0 - d, d, k0);
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        long long m_, k_; scanf("%lld%lld", &m_, &k_);
        m = m_;
        printf("%lld\n", k_ - (long long)calc(k_ - 1, 1, k_));
    }
}