题目链接

告诉你 $p, x$ 求最小的 $a, b$,使得 $a \equiv bx(mod\ p)$。

由于 $\frac{a}{b}\equiv x(mod \ p)$,引入 $y$ 有 $a=bx-py$,

由于 $0<bx-py<b$ 可得 $\frac{p}{x}<\frac{b}{y}<\frac{p}{x-1}$,这个可以辗转相除法搞。

我们考虑我们要找到最小的 $b, c$ 使得 $\frac{p}{x}<\frac{b}{c}<\frac{q}{y}$ 。

分为下面几种情况

  1. 当 $\left \lfloor \frac{p}{x} \right \rfloor \neq \left \lfloor \frac{q}{y} \right \rfloor $ 时,那么在 $\left[\frac{p}{x}, \frac{q}{y}\right]$ 中肯定存在整数 $\left \lfloor \frac{p}{x} \right \rfloor + 1$,那么我们令 $\frac{b}{c} = \left \lfloor \frac{p}{x} \right \rfloor + 1$ ,即$b=\left \lfloor \frac{p}{x} \right \rfloor + 1,\ c=1$ 。
  2. 当 $\left \lfloor \frac{p}{x} \right \rfloor = \left \lfloor \frac{q}{y} \right \rfloor $ 时,记 $z_{1} = \left \lfloor \frac{p}{x} \right \rfloor$,我们在不等式的三边同时减去 $z_{1}$ ,不等式变为 $\frac{p-z_{1}x}{x}<\frac{b-z_{1}c}{c}<\frac{q-z_{1}y}{y}$ 。我们将不等式三边取倒数,那么不等式变为 $\frac{y}{q-z{1}y}<\frac{c}{b-z_{1}c}<\frac{x}{p-z_{1}x}$ ,此时我们继续解这个新的方程即可。
#include<bits/stdc++.h>

using namespace std;

//解满足 p/x < b/c < q/y 的最小的b和c, 都减去z1然后倒过来
void solvegcd(long long p, long long x, long long &b, long long &c, long long q, long long y) {
    long long z1 = p / x;
    long long z2 = q / y;
    if (z1 != z2)
        return b = z1 + 1, c = 1, void();
    long long pp = y;
    long long xx = q - z1 * y;
    long long bb = c;
    long long cc = b - z1 * c;
    long long qq = x;
    long long yy = p - z1 * x;
    solvegcd(pp, xx, bb, cc, qq, yy);
    b = cc + z1 * bb;
    c = bb;
}

long long p, x, b, c;

int main() {
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%lld%lld", &p, &x);
        b = 0;
        c = 0;
        solvegcd(p, x, b, c, p, x - 1);
        long long a = b * x - c * p;
        printf("%lld/%lld\n", a, b);
    }
    return 0;
}