AC(带注释)

我是小学生  •  2天前


include <bits/stdc++.h>

using namespace std;

//计算最大公约数 int gcd(int a, int b) {

while (b != 0) {
	int temp = b;
	b = a % b;
	a = temp;
}
return a;

}

int main() {

int A, B, L;
cin >> A >> B >> L;

int b_a = -1, b_b = -1;
double mf = DBL_MAX; // 初始化一个大的差值
double tar = static_cast<double>(A) / B;//转为浮点数除法防止精度丢失

for (int b = 1; b <= L; ++b) {
	// 计算A'的下界
	int num = A * b;
	int a_min = (num + B - 1) / B; // 向上取整

	// A'不能超过L(防止越界)
	if (a_min > L) {
		continue;
	}

	// 检查从a_min到L的所有A'
	for (int a = a_min; a <= L; ++a) {
		// 确保A'和B'互质
		if (gcd(a, b)!=1) {
			continue;
		}

		// 计算当前比例与目标比例的差值
		double cur = static_cast<double>(a) / b;
		double df = cur - tar;

		// 更新最优解
		if (df < mf) {
			mf = df;
			b_a = a;
			b_b = b;
		}
	}
}

cout << b_a << " " << b_b << endl;

return 0;

}


评论:

请先登录,才能进行评论