思路与算法

枚举分子分母各1至L，检查互质和不小于原比例，以交叉乘积比较候选；与既有比例缩放或组合系数题不同。

按上述模型建立状态或枚举对象，依代码中的顺序处理输入并输出完整答案。

正确性说明

枚举覆盖所有允许的互质分子分母，对不低于A/B的分数取最小就是最小非负误差；交叉相乘保持比较精确。

复杂度

O(L² log L)时间，O(log L)最大公约数递归栈；其余常数空间。

易错点

检查不等号方向为候选不小于原比例。分子分母都受L限制，非只限制分母。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int gcd1(int a, int b) {
    return b ? gcd1(b, a % b) : a;
}
int main() {
    long long a, b;
    int l;
    cin >> a >> b >> l;
    int x = 0, y = 1;
    for (int i = 1; i <= l; i++)
        for (int j = 1; j <= l; j++)
            if (gcd1(i, j) == 1 && i * b >= a * j && (!x || 1LL * i * y < 1LL * x * j)) {
                x = i;
                y = j;
            }
    cout << x << ' ' << y << "\n";
}