题目描述

no

样例

i:1498 902 10
o: 5 3

算法1

(暴力枚举) $O(n^2)$

根据题目中要求:
要求在A′和B′均不大于L且A′和B′互质（两个整数的最大公约数是1）的前提下，A′/B′≥A/B且A′/B′−A/B的值尽可能小。
表明循环条件为i<=l j<=l
然后写求两数最大公约数函数:
int zdgys(int m,int n){
if(n==0){
return m;
}else{
return zdgys(n,m%n);
}

}
辗转相除法，递归实现

此题使用循环嵌套即可实现
循环内if判断是否满足i/(double)j>=a/(double)b且i，j的最大公约数为1即可数组记录结果 //注意把int转double，数组不能动态分配
最后循环取数组中数，使(double)i/j=(double)a/b最小，记录下标，输出。
但要注意
时间复杂度分析：no

C++ 代码

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
int zdgys(int m,int n){
if(n==0){
return m;
}else{
return zdgys(n,m%n);
}

}
int main(){
int a,b,l;
cin>>a>>b>>l;
int c[100001],d[100001],t=0;
for(int i=1;i<=l;i){
for(int j=1;j<=l;j){
if(i/(double)j>=a/(double)b&&zdgys(i,j)==1){
c[t]=i;
d[t]=j;

            t++;

        }
    }
}
int k=0;
for(int h=0;h<t;h++){
    if(c[h]/(double)d[h]-(double)a/b<c[k]/(double)d[k]-(double)a/b)k=h;
}

// cout<<c[0]<<’ ‘<<d[0]<<endl;
cout<<c[k]<<” “<<d[k]<<endl;

return 0;

}