【題解】ZeroJudge c160: NOIP2014 2.比例简化

#include <iostream>
using namespace std;

int gcd(int m, int n) {
    while (m != n) {
        if (m > n) m = m - n;
        else n = n - m;
    }
    return m;
}
int main() {
    int A, B, L;
    int A1, B1;
    int A2, B2;
    double r0, r1;
    
    while (cin >> A >> B >> L) {
        double mini = 100000.0;
        for (A1 = 1; A1 <= L; A1++) {
            for (B1 = 1; B1 <= L; B1++) {
                r0 = (double)A / (double)B;
                r1 = (double)A1 / (double)B1;
                if (r1 < r0) continue;
                if (gcd(A1, B1) != 1) continue;
                if (r1 - r0 < mini) {
                    mini = r1 - r0;
                    A2 = A1;
                    B2 = B1;
                }
            }
        }
        cout << A2 << " " << B2 << "\n";
    }
    return 0;
}

def myGCD(x, y):
    while x and y:
        tmp = x
        x = x % y
        y = y % tmp
        continue
    return x+y

# main program
A, B, L = map(int, input().split())
C = A / B
mn = 1e5
A2 = 1
B2 = 1
for A1 in range(1, L+1):
    for B1 in range(1, L+1):
        C1 = A1 / B1
        if C1 < C:
            continue
        if myGCD(A1, B1) != 1:
            continue
        if (C1 - C < mn):
            mn = C1 - C
            A2 = A1
            B2 = B1
print(A2, B2)