3039.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 48 行

Problem Id:3039  User Id:fzk 
Memory:60K  Time:431MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <math.h>
int gcd( int a, int b ) {
	int t;
	while( b % a ) {
		t = a;
		a = b%a;
		b = t;
	}
	return a;
}

int main() {
	int n, k, i, j, bi, bj;
	double s, best = 999999999;
	scanf( "%d%d", &n, &k );
	//n/k = j/i
	s = 1.0*n/k;
	for( i=1; i<=32767; i++ ) 
	if( i != k ) {
		j = int(i*s+1e-7);
		while( j > 0 && gcd( j, i ) != 1 )
			j--;

		if( j > 0 && fabs( j*1.0/i - s ) < best )
			bi = i, bj = j, best = fabs( j*1.0/i - s );

		j = int(i*s+1e-7) + 1;
		while( j < i && gcd( j, i ) != 1 )
			j++;

		if( j <= 32767 && fabs( j*1.0/i - s ) < best )
			bi = i, bj = j, best = fabs( j*1.0/i - s );
	}

	printf( "%d %d\n", bj, bi );
	return 0;
}