Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

0ms很容易婀!

Posted by KatrineYang at 2016-07-10 16:21:48 on Problem 1079
代妈如下~
没有用浮点,也不需要long long int,0msAC
#include <iostream>
using namespace std;

int ABS(int a){
	return a>=0? a: -a;
}

int GCD(int a, int b){
	if(a == 0) return b;
	if(b == 0) return a;
	if(a > b) return GCD(b, a%b);
	return GCD(a, b%a);
}

int main() {
	int A, B;
	while(cin >> A >> B){
		if(A == 0 && B == 0) return 0;
		int gcd = GCD(A, B);
		A /= gcd;
		B /= gcd;
		int a0, b0;
		b0 = 1;
		int temp = A/B;
		if(ABS(A-(temp+1)*B) <= ABS(A-temp*B)) a0 = temp+1;
		else a0 = temp;
		cout << a0 << "/" << 1 << endl;
		for(int b1 = 2; b1 < B; b1++){
			int a1 = b1 * A / B;
			if(ABS((a1+1)*B-b1*A) <= ABS(a1*B-b1*A)) a1++;
			if(GCD(a1, b1) > 1) continue;
			if(b0*ABS(a1*B-b1*A) < b1*ABS(a0*B-b0*A)){
				a0 = a1;
				b0 = b1;
				cout << a0 << "/" << b0 << endl;
			}
		}
		cout << A << "/" << B << endl;
		cout << endl;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator