最接近的分数题解

学生版：

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b) {
    while(b)
    {
        int t=b;
        b=a%b;
        a=t;
    }
    return a;
}
int main()
{
    int n,a,b;
    cin>>n>>a>>b;
    int bfz=0,bfm=1;
    for(int d=n;d>=1;d--)
    {
        int c=(a*d-1)/b;
        if(c<0) continue;
        if(gcd(c,d)==1) {
            if(c*bfm>d*bfz) {
                bfm=d;
                bfz=c;
            }
        }
    }
    cout<<bfz<<" "<<bfm<<endl;
    return 0;
}

老师版：

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b) {
    //return b==0?a:gcd(b,a%b);
    while(b)
    {
        int t=b;
        b=a%b;
        a=t;
    }
    return a;
}
int main()
{
    int n,a,b;
    cin>>n>>a>>b;
    //定义一个最优的C/D，不停更新最值
    int bfz=0,bfm=1;//初始最优状态
    for(int d=n;d>=1;d--)//d分母
    {
        //c/d<a/b->c<a*d/b;严格小于非小于等于
        int c=(a*d-1)/b;
        if(c<0) continue;
        //是否是最简
        if(gcd(c,d)==1) {
            //更新最优分数bfz/bfm<c/d->d*bfz<c*bfm
            if(c*bfm>d*bfz) {
                //更新记录
                bfm=d;
                bfz=c;
            }
        }
    }
    cout<<bfz<<" "<<bfm<<endl;
    return 0;
}