Description
分数 给你4个正整数a，b，c，d，求一个最简分数 p / q满足 a / b < p / q < c / d，若有多组解，输出q最小的一组，若仍有多组解，输出p最小的一组。 Input
本题有多组数据，有若干行，每行4个数a，b，c，d。以文件的末尾作为结束。 Output
对于输入的每组数据输出一个最简分数p/q。 Sample Input
1 3 1 2
2 1 3 1
2 1 4 1
1000 1001 1001 1002
Sample Output
2/5
5/2
3/1
2001/2003
数据约定
对于100%的数据 1 < = a，b，c，d < = 109 对于100%的数据 1 < = 数据组数<=500 数据保证至少存在一个最简分数符合条件。HINT
Source
可以，很强势，说好的类欧实际上只要随便手玩一下就能出来的东西，分类讨论一下就好了。 之所以是类欧是因为类欧的定义就是把题目问题缩小规模解决的算法。 过程如下（偷图from ymw）
#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; typedef long long ll; ll a,b,c,d; ll p,q; inline ll gcd(ll a,ll b) { if (!b)return a; else return gcd(b,a%b); } inline void hj(ll &a,ll &b) { ll d=gcd(a,b); a/=d,b/=d; } inline void solve(ll a,ll b,ll c,ll d,ll &p,ll &q) { hj(a,b),hj(c,d); ll x=a/b+1,y=c/d+(c%d>0)-1; if (x<=y)p=x,q=1; else if (!a)p=1,q=d/c+1; else if (a<=b&&c<=d)solve(d,c,b,a,q,p); else solve(a%b,b,c-d*(a/b),d,p,q),p+=q*(a/b); } int main() { while (scanf("%lld%lld%lld%lld",&a,&b,&c,&d)!=EOF) { solve(a,b,c,d,p,q); printf("%lld/%lld\n",p,q); } }