本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：51nod 1187
正解：类扩展欧几里得
解题报告：
前几天的那个部分分可以用这个算法来做，不过是在$LCT$上维护这个东西，差不多啦==
因为我们需要求得一个指定范围内的分母最小的分数，考虑用类似放缩法的做法，和$exgcd$也很类似？
每次传一个$(a,b,c,d)$的四元组下去就好了。
当$a=0$时，可以发现$q>frac{d*p}{c}$，显然$p$取$1$时，$q$最优。
当$a>=b$时，说明整数部分可以提出来，注意这里不是同时提各自的整数部分，而是都提出一个$a/b$的整数部分，递归做下去，注意做完的时候还要再加上一个$a/b$的部分。
如果上述条件都不满足且$c>d$，那就说明此时的分母已经可以唯一确定为$1$了。
因为一个$>1$，一个$<1$，那最小的分母当然是$1$啦。
否则，我们就把整个分数倒过来，取个倒数之后继续搞事情...
对于最后一种情况，记得做完的时候$swap$一下分子分母就好了。
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long LL;
LL p,q;
inline LL getint(){
LL w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void solve(LL a,LL b,LL c,LL d){
if(a==0) {
p=1; q=d/c+1;
return ;
}
else if(a>=b) {
solve(a%b,b,c-(a/b)*d,d);
p+=(a/b)*q;
return ;
}
else if(c>d) {//!!!
p=1; q=1;
return ;
}
else {
solve(d,c,b,a);
swap(p,q);
}
}
inline void work(){
int T=getint(); LL a,b,c,d;
while(T--) {
a=getint(); b=getint(); c=getint(); d=getint();
p=0; q=0;
solve(a,b,c,d);
printf("%lld/%lld
",p,q);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1187.in","r",stdin);
freopen("1187.out","w",stdout);
#endif
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。