6624 fraction

存dls板子，dlstxdy

已知 x p，求满足  并且  并且 b 是最小正整数的最简分数。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
void fun(ll pa, ll pb, ll qa, ll qb, ll& x, ll& y)
{
    ll z = (pa + pb - 1) / pb;
    if (z <= qa / qb) 
    {
        x = z; y = 1;
        return;
    }
    pa -= (z - 1) * pb; qa -= (z - 1) * qb;
    fun(qb, qa, pb, pa, y, x);
    x += (z - 1) * y;
}
int main() 
{ 
int T;
scanf("%d",&T);
while (T--)
{
    // z / x === a (% mod)
    ll a, mod, x, y;
    scanf("%lld%lld", &mod, &a);
    fun(mod, a, mod, a - 1, x, y);
    ll z = x * a - mod * y;
    printf("%lld/%lld\n", z, x);
}}