L小于等于100,所以可以直接枚举出答案,代码参考了Y总。
本题用到 gcd 函数求两个数的最大公约数,gcd函数原题:872. 最大公约数
#include <iostream>
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 = 1e6;
for (int i = 1; i <= L; i ++ ) //逐个枚举要求的A'和B'
for (int j = 1; j <= L; j ++ )
if (gcd(i, j) == 1) //判断i与j是否互为质数,即最大公约数为1
{
double x = i * 1.0 / j; //小x代表估计比值
double X = A * 1.0 / B; //大X代表实际比值
if (x >= X && x - X < delta) //估值要对真实值取上界且与真实值相差尽可能小
{
delta = x - X;
a = i, b = j; //记录最接近的估值
}
}
cout << a << ' ' << b << endl;
return 0;
}