首页 > ACM题库 > HDU-杭电 > HDU 4180-RealPhobia-数论-[解题报告]HOJ
2015
05-23

HDU 4180-RealPhobia-数论-[解题报告]HOJ

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

题意为给定一个数(a/b),求另一个(c/d) ,要求d  <  b  , 并且要求fabs( a / b – c / d ) 要最小 ;

当 a 与 b 互质的时候 ,有a * d + 1 == b * c  || a * d == b * c +  1 ;  然后通过exgcd 求出c 和 d 然后比较d的大小,最后输出结果;

需要注意的是,这只是其中的一种情况, 当a 和 b 存在最大公约数时,直接整除即可,当a为1 的时候,因为分子已经处于最小的状态,因此只需要改变分母的大小即可,有因为d < b 并且要求最小,所以b   –   1;

#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 ;
} 	

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/bo_jwolf/article/details/9034589