题意:分数取模的意义是 a/b = x(mod p),告诉你 p和x,求最小的分数解a/b
解:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void gao(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;
gao(qb,qa,pb,pa,y,x);
x+=(z-1)*y;
}
ll p,a,x,y;
int main()
{
int _;
for(scanf("%d",&_);_;_--){
scanf("%lld %lld",&p,&a);
gao(p,a,p,a-1,x,y);
ll z = x*a - y*p;
printf("%lld/%lld\n",z,x);
}
return 0;
}