首页c语言编程题目：现给出整数A ， B ，以及一个上限 L ，请你将 A 比 B 化简为 A′ 比 B′ ，要求在 A′ 和 B′ 均不大于 L 且 A′ 和 B′ 互质（两个整数的最大公约数是 1）的前提下，A′/B′≥A/B 且 A′/B′−A/B 的值尽可能小。

c语言编程题目：现给出整数A ， B ，以及一个上限 L ，请你将 A 比 B 化简为 A′ 比 B′ ，要求在 A′ 和 B′ 均不大于 L 且 A′ 和 B′ 互质（两个整数的最大公约数是 1）的前提下，A′/B′≥A/B 且 A′/B′−A/B 的值尽可能小。

时间: 2024-05-02 16:21:41 浏览: 70

思路：首先，我们可以简单地通过不断地约分 A 和 B 来使得 A 和 B 的最大公约数为 1。接下来，我们需要使得 A′ 和 B′ 均不大于 L 且 A′ 和 B′ 互质。我们可以考虑枚举 B′ 的值，然后通过扩大 A′ 和 B′ 的倍数来得到 A′ 和 B′ 互质的结果。具体地，对于每个枚举的 B′，我们在 [1, L/B′] 的范围内枚举 A′ 的值，然后计算 A′/B′，并找到最大的 A′/B′ 满足 A′ 和 B′ 互质。最后，我们需要在所有可能的 A′/B′ 中找到最接近 A/B 的值。代码实现： ```c #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, b = B; int d = gcd(a, b); a /= d, b /= d; for (int i = 1; i <= L / b; i++) { int j = a * i / b; if (gcd(i, j) != 1) continue; if (a * i - b * j < a * L - b * (j * b + b - 1)) { a = i; b = j; } } printf("%d %d\n", a * B, b * B); return 0; } ```

阅读全文