分析与解答

其实如果数据足够大，穷举就会超时，但是有一种O(2n)的算法，用到的是逼近法：

i和j从1开始，如果i/j<a/b那么i++(如果还不够大，那么分子加一)，如果i/j>=a/b那么j++(如果还打了，分子就不加了，加分母)并且与ans判断取小的

这里注意一点，浮点数运算是不精确的，判断i/j>=a/b要适当变形：

i≥j×a/b

i×b≥j×a

这样就只需要做整数乘法即可

AC代码

#include <iostream>
using namespace std;
int main()
{
    int a, b, c, d, n;//a,b表示输入进来的，c, d表示题目中的a',b', 也就是上文中的i, j, n就是上限啦
    cin >> a >> b >> n;//输入
    int ans1 = n, ans2 = 1;//将ans赋值为不超过上限的最大值
    c = d = 1;//初值为1
    while (c <= n && d <= n)//不能超过上限
    {
        if (a * d <= b * c)//如果大于等于(用上面推出的公式)
        {
            if (c * ans2 < d * ans1)//看是否能更新答案(还是用上面推出的公式)
                ans1 = c, ans2 = d;//更新
            d++;//分母加1
        }
        else//如果小于
            c++;//分子加1
    }
    cout << ans1 << " " << ans2;//输出答案
    return 0;
}

这道题的L范围是很有良心的，L小于等于100，则可以直接枚举分子和分母。可以看出分子分母的枚举范围都是1到L，之后可以写一个最大公约数，判断分子分母的最大公约数是否为1（可以用辗转相除法）。然后到了本题的第一个坑：分子分母的比值要大于A和B的比值。根据小学数学的交叉相乘法，就可以将这个式子写成：现分子B<=现分母A。到了最后一个条件了，使分子分母的比值要尽可能地接近A和B的比值，可以把所有符合上面两个条件的分子分母在一起比较，选出最优解。

附上代码：

#include<cstdio>
using namespace std;
int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
int main()
{
        int i,j,a,b,ansa,ansb,l;
        scanf("%d%d%d",&a,&b,&l);
        ansa=l;ansb=1;
        for(i=1;i<=l;i++)
                for(j=1;j<=l;j++)
                        if(gcd(i,j)==1&&i*b>=j*a&&i*ansb<j*ansa)
                        {
                                ansa=i;
                                ansb=j;
                        }
        printf("%d %d",ansa,ansb);
        return 0;
}

注意到L的范围很小，直接两个循环枚举A'和B'，然后用两个限制条件来约束答案，两个限制条件就是$A’/B’≥ A/B$且$A’/B’- A/B$的值尽可能小

很简单的题，注意该double计算的弄好即可，代码不放了