算法知识点: 枚举，欧几里得算法，数论)

复杂度：

解题思路：

由于 在100以内，因此可以枚举 的所有组合，然后判断：

  • 是否互质；
  • 是否大于等于 ，并且最小

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;
}


另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ