c语言编程题目: 现给出整数A , B ,以及一个上限 L ,请你将 A 比 B 化简为 A′ 比 B′ ,要求在 A′ 和 B′ 均不大于 L 且 A′ 和 B′ 互质(两个整数的最大公约数是 1)的前提下,A′/B′≥A/B 且 A′/B′−A/B 的值尽可能小。
时间: 2024-06-01 10:10:30 浏览: 25
思路:
首先,A/B 可以化简为最简分数,即分子分母互质。
然后,我们可以枚举 A′ 和 B′,使它们都小于等于 L,且互质。
对于每一组 A′ 和 B′,我们计算 A′/B′ 与 A/B 的差值,取差值最小的一组作为答案。
代码实现:
#include <stdio.h>
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int A, B, L;
scanf("%d%d%d", &A, &B, &L);
int a = A / gcd(A, B), b = B / gcd(A, B); // 化简 A/B
int ans_a = a, ans_b = b;
for (int i = 1; i <= L && i <= b; i++) { // 枚举 B′
for (int j = 1; j <= L && j <= a; j++) { // 枚举 A′
if (gcd(i, j) == 1 && (long long)j * b > (long long)i * a) { // 互质且 A′/B′≥A/B
if ((long long)j * b * (ans_a - ans_b) > (long long)i * a * (j - i)) { // 更新答案
ans_a = j;
ans_b = i;
}
}
}
}
printf("%d %d\n", ans_a * gcd(A, B), ans_b * gcd(A, B)); // 输出化简后的 A 和 B
return 0;
}