算法

(枚举,欧几里得算法,数论) $O(L^2)$

由于 $L$ 在100以内，因此可以枚举 $A’, B’$ 的所有组合，然后判断：

• $A’, B’$ 是否互质；
• $\frac{A’}{B’}$ 是否大于等于 $\frac{A}{B}$，并且最小

感谢@[zhangmingjie]同学的提示，上述算法可以省去对于 $A’, B’$ 是否互质的判断：

• 我们分别从小到大枚举 $A’, B’$，那么当 $(A’, B’) = d > 1$ 时，我们一定在此之前先枚举了 $\frac{A’}{d}$ 和 $\frac{B’}{d}$，这两组的比值是相同的，所以我们一定不会选择前一组，即一定不会选择不互质的一组。

时间复杂度

$A’, B’$ 总共有 $L^2$ 种组合，因此总时间复杂度是 $O(L^2logL)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int A, B, L;
    cin >> A >> B >> L;

    int a, b;
    double delta = 1e9;
    for (int i = 1; i <= L; i ++ )
        for (int j = 1; j <= L; j ++ )
            if (gcd(i, j) == 1)
            {
                double x = i * 1.0 / j;
                double X = A * 1.0 / B;

                if (x >= X && x - X < delta)
                {
                    delta = x - X;
                    a = i, b = j;
                }
            }

    cout << a << ' ' << b << endl;

    return 0;
}