题解 P2118 【比例简化】

· · 题解

【问题分析】 这题用于包装的背景很贴切——至少是有一定实用价值的。一道看似无从下手的题目，把它的包装皮撕开以后，发现又可以以“1≤L≤100”这个较小的数据范围作为突破口，枚举所有合法的A’和B’即可。 具体算法如下： ①从1~L 分别枚举A’、B’；对于每一对A’、B’，判断是否满足“A'和B'互质且A'/B'≥A/B”，若满足，则②，否则继续枚举； ②判断A'/B'-A/B 是否比当前差值小，若是，更新A’、B’和差值，否则①。

#include <iostream>
using namespace std;
int fun(int a,int b)
{
    int r;
    r=a%b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}

int main()
{
    int a,b,l;
    int aa,bb;
    double radio,min;

    cin>>a>>b>>l;

    radio=1.0*a/b;
    min=l;
    for(int i=1;i<=l;i++)
        for(int j=1;j<=l;j++)
        {
            if(fun(i,j)==1 && 1.0*i/j>=radio){
                if(1.0*i/j-radio<min){
                    min=1.0*i/j-radio;
                    aa=i;
                    bb=j;
                }
            }
        }

    cout<<aa<<" "<<bb;

    return 0;
}