2015
05-23

# RealPhobia

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:
1. 0 < C < D < B, and
2. the error |A/B – C/D| is the minimum over all possible values of C and D, and
3. D is the smallest such positive integer.

The input starts with an integer K (1 <= K <= 1000) that represents the number of cases on a line by itself. Each of the following K lines describes one of the cases and consists of a fraction formatted as two integers, A and B, separated by “/” such that:
1. B is a 32 bit integer strictly greater than 2, and
2. 0 < A < B

The input starts with an integer K (1 <= K <= 1000) that represents the number of cases on a line by itself. Each of the following K lines describes one of the cases and consists of a fraction formatted as two integers, A and B, separated by “/” such that:
1. B is a 32 bit integer strictly greater than 2, and
2. 0 < A < B

3
1/4
2/3
13/21

1/3
1/2
8/13

http://acm.hdu.edu.cn/showproblem.php?pid=4180

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std ;
#define INT __int64
INT x , y ;
INT exgcd( INT a , INT b ,INT &x , INT &y )
{
if( b == 0 )
{
x = 1 ;
y = 0 ;
return a ;
}
INT r = exgcd( b , a % b , x , y ) ;
INT t = x ;
x = y ;
y = t - a / b * y ;
return r ;
}

int main()
{
int Case ;
INT m , n ;
cin >> Case ;
while( Case-- )
{
scanf( "%I64d/%I64d" ,&m , &n );
INT d = exgcd( m , n , x , y) ;
if( d != 1 )
{
cout << m / d << "/" << n/d << endl ;
continue ;
}
if( m == 1 )
{
cout << "1/" << n - 1 << endl ;
continue ;
}
INT x1 = ( x + n ) % n ;
INT y1 = ( -y + m ) % m;
INT x2 = ( -x + n ) % n ;
INT y2 = ( y + m ) % m ;
if( x1 > x2 )
printf( "%I64d/%I64d\n" , y1 , x1 ) ;
else
printf( "%I64d/%I64d\n" ,  y2 , x2 ) ;
}
return 0 ;
}