SPOJ上的每个题目都做得我泪牛满面。
这个题目也是的。题目意思是给你两个分数a/b和c/d，要你求出一个分数p/q，使得a/b<p/q<c/d，且p最小。
看完题目后半天都没有任何思路哦。于是无奈只好去网上找题解咯。
终于找到一个神牛的题解，并且自己终于把那个东西给看懂了。
下面写下我自己的理解吧。
首先对于我们不要急于求分子，我们只要求出分母q，分子就可以直接用q*a/b+1表示了（想想为什么呢？因为要最小的）。
那么要求这个分母，首先把第一个分数变成0-1之间，即k=a/b，a-=b*k，同时第二个分数也要做相同的改变，c-=d*k；
这样不等式的方向都是没有变化的。这时候要是c/d>1，也就是说c>d，那么就说明p/q=1；
否则我们可以把这个不等式式同时取倒数变为 d/c<q/p<b/a， 这时候我们可以再次递归求解p哦，有了p，q=p*d/c+1；
恩大概就是这样，具体的证明我也无法给出，好好理解一下吧。
1 #include <iostream> 2 using namespace std; 3 typedef long long ll; 4 5 ll dfs(ll a,ll b,ll c,ll d) 6 { 7 ll k=a/b; 8 a-=b*k,c-=d*k; 9 if (c>d) return 1; 10 return dfs( d,c,b,a)*d/c+1; 11 } 12 13 int main() 14 { 15 ll a,b,c,d,p,q; 16 while (cin>>a>>b>>c>>d) 17 { 18 q=dfs(a,b,c,d); 19 p=q*a/b+1; 20 cout<<p<<'/'<<q<<endl; 21 } 22 return 0; 23 }