題目大意：
給出一個(gè)分?jǐn)?shù)，比如1498/902。求出當(dāng)分母分別為1, 2, ....的時(shí)候，最接近1498/902的分?jǐn)?shù)。
比如：
當(dāng)分母為1的時(shí)候，最接近1498/902的分?jǐn)?shù)為 1/1。
當(dāng)分母為2的時(shí)候，最接近1498/902的分?jǐn)?shù)為 3/2。
當(dāng)分母為3的時(shí)候，最接近1498/902的分?jǐn)?shù)為 5/3。
。。。
思路：
不要用高精度哦，直接模擬分?jǐn)?shù)的操作最好了。
#include <stdio.h>
#include <math.h>
struct frac 
{
__int64 up, down;
};
__inline __int64 gcd(__int64 a, __int64 b)
{
__int64 r;
if (a < b) {
r = a;
a = b;
b = r;
}
while (1) {
r = a % b;
if (!r)
return b;
a = b;
b = r;
}
}
__inline struct frac frac_init(__int64 up, __int64 down)
{
__int64 r, s;
struct frac f;
r = up ? gcd(up, down) : 1;
if (r < 0)
r = -r;
f.up = up / r;
f.down = down / r;
return f;
}
__inline struct frac frac_sub(struct frac fa, struct frac fb)
{
return frac_init(fa.up*fb.down-fa.down*fb.up, fa.down*fb.down);
}
__inline __int64 frac_cmp(struct frac fa, struct frac fb)
{
return frac_sub(fa, fb).up;
}
__inline struct frac frac_abs(struct frac f)
{
if (f.up < 0)
f.up = -f.up;
return f;
}
int main()
{
__int64 up, down;
struct frac target, min_dis, f, dis;
while (scanf("%I64d%I64d", &up, &down) != EOF) {
target = frac_init(up, down);
min_dis.down = 1;
min_dis.up = (__int64)1e15;
for (down = 1; down <= target.down; down++) {
up = (down*target.up)/target.down;
if (((down*target.up)%target.down)*2 >= target.down)
up++;
f = frac_init(up, down);
dis = frac_abs(frac_sub(f, target));
if (frac_cmp(dis, min_dis) < 0) {
printf("%I64d/%I64d\n", f.up, f.down);
min_dis = dis;
}
}
printf("\n");
}
return 0;
}