HDU RealPhobia

题目大意：Bert 是一位非常害怕浮点运算的程序员。Bert 已经相当成功地使用有理数来编写他的程序，但他不喜欢分母变大。你的任务是帮助 Bert 编写一个程序，减少有理数的分母，同时引入尽可能小的误差。对于有理数 A/B，其中 B > 2,0 < A < B，您的程序需要确定一个有理数 C/D，使得：
1. 0 < C < D < B
2. 误差 |A/B - C/D |是 C 和 D 的所有可能值的最小值
3.D 是最小的正整数

思路：这题需要分类讨论。若 A 和 B 的最大公约数不为 1 时，直接约分输出即可。若 A 和 B 的最大公约数不为 1 时，有一种特殊情况就是当 A = 1 时，又因为 D < B ，所以 D = B -1 ，C = 1；当 A ! = 1 时，由条件 2 可以得到 | A*D - B*C | = 1 （注意这个式子中间是负号），这时保证了分子最小，但我们还要让分母尽可能的大，即 D 要 大一些 。我们用扩展欧几里得可以求出两对{ C ， D }，取 两个 D 里大的那对{ C ， D } 即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return a;}int gcd=exgcd(b,a%b,y,x);y-=a/b*x;return gcd;
}
signed main(){int _;cin >> _;while(_--){int a,b,x,y;char s;cin >> a >> s >> b;int gcd=exgcd(a,b,x,y);if(a==1) cout << "1/" << b-1 << endl;else if(gcd!=1) cout << a/gcd << "/" << b/gcd << endl;else{int d1=(x+b)%b,c1=(a*d1-1)/b;//a*d1-b*c1=1,c1=(a*d1-1)/bint d2=(-x+b)%b,c2=(a*d2+1)/b;//b*c2-a*d2=1,c2=(1-a*(-d2))/bif(d1>d2) cout << c1 << "/" << d1 << endl;else cout << c2 << "/" << d2 << endl;}}return 0;
}