# include <stdio.h>
typedef long long int LL;
/***************************************/
LL Min(LL x, LL y)
{
return x < y ? x : y;
}
LL Max(LL x, LL y)
{
return x > y ? x : y;
}
LL gcd(LL x, LL y)
{
if (!y) return x;
return gcd(y, x%y);
}
LL ex_gcd(LL a,LL b,LL &x,LL &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
LL g,t;
g=ex_gcd(b,a%b,x,y);
t=x;
x=y;
y=t-a/b*y;
return g;
}
LL niyuan(LL b,LL p)
{
LL x,y;
ex_gcd(b,p,x,y);
return x=(x%p+p)%p;
}
/***************************************/
struct frac
{
LL n, d;
} ;
LL A, B, C, D;
LL LLabs(LL x)
{
return x>0 ? x:-x;
}
void slim(frac &x)
{
LL tmp = LLabs(gcd(x.d, x.n));
x.d /= tmp;
x.n /= tmp;
}
frac dif(frac x, frac y)
{
frac z;
z.d = x.d * y.d;
z.n = LLabs(x.n*y.d-x.d*y.n);
slim(z);
return z;
}
int cmp(frac x, frac y)
{
return x.n*y.d - x.d*y.n>0 ? 1:0;
}
frac cal(frac x, frac y, frac BA)
{
return cmp(dif(x, BA), dif(y, BA)) ? y:x;
}
void solve(void)
{
frac BA;
BA.n = A, BA.d = B;
LL n1 = niyuan(B, A);
if (n1 == 0) n1 = A;
LL d1 = (B*n1-1) / A;
LL d2 = niyuan(A, B);
if (d2 == 0) d2 = B;
LL n2 = (A*d2-1) / B;
frac a, b;
a.n = n1, a.d = d1;
b.n = n2, b.d = d2;
slim(a), slim(b);
frac ans = cal(a, b, BA);
printf("%lld/%lld\n", ans.n, ans.d);
}
/***************************************/
int main()
{
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while (T--)
{
scanf("%lld/%lld", &A, &B);
LL tmp = gcd(A, B);
if (tmp != 1)
{
printf("%lld/%lld\n", A/tmp, B/tmp);
}
else solve();
}
return 0;
}
Bert is a programmer with a real fear of floating point arithmetic. Bert has quite
successfully used rational numbers to write his programs but he does not like it when the
denominator grows large.
Your task is to help Bert by writing a program that decreases the denominator of a
rational number, whilst introducing the smallest error possible. For a rational number A/B,
where B > 2 and 0 < A < B, your program needs to identify a rational number C/D such
that:
-
0 < C < D < B, and
- the error
| A/B - C/D| is the minimum over all possible values of C and D, and
-
D
is the smallest such positive integer.
Output
For each case, the output consists of a fraction on a line by itself. The fraction should
be formatted as two integers separated by `/'.
Sample Output
1/3
1/2
8/13
posted on 2012-09-15 17:26
yajunw 阅读(282)
评论(0) 编辑 收藏 引用