寻找满足最大公因数条件的最小c值算法解析

根据题意，需要找到最小的 c（c≠b），使得 gcd(a, c) = b。 因为 a > b，且 gcd(a, c) = b，所以 c 必须是 b 的倍数，且 c 与 a/b 互质。 最小符合条件的 c 通常为 2b，但需检查是否满足条件。若 2b 不满足（即 gcd(a, 2b) ≠ b），则尝试 3b、4b 等，直到找到第一个满足条件的。 具体推理： 令 a = b * m（m > 1 且 m 为整数）。 需要 c = b * k，其中 k 为正整数，且 k ≠ 1（因为 c≠b），且 gcd(m, k) = 1。 最小 k 从 2 开始尝试，找到第一个与 m 互质的 k。 例如： a=12, b=4 → m=3，k=2 时 gcd(3,2)=1，c=8。 a=10, b=5 → m=2，k=2 时 gcd(2,2)=2 ≠1，k=3 时 gcd(2,3)=1，c=15。 a=15, b=6 → m=2.5 不合法，因为 b 必须整除 a，所以输入保证 a 是 b 的倍数。 由于题目保证 a > b 且 c<1000，可用循环从小开始尝试。 ## 实现代码（C语言） ```c #include <stdio.h> int gcd(int x, int y) { while (y) { int t = x % y; x = y; y = t; } return x; } int main() { int a, b; scanf("%d %d", &a, &b); int m = a / b; int k = 2; while (1) { if (gcd(m, k) == 1) { printf("%d\n", b * k); break; } k++; } return 0; } ``` ## 示例运行 输入： 12 4 输出： 8 输入： 10 5 输出： 15 输入： 15 9 输出： 27（因为 m=5/3 不是整数？检查：15/9=1.666，不合法，所以输入必然满足整除。这里举例用合法数据如 a=18, b=6 → m=3，k=2得到12，符合。） ######[AI问答 | 571点数解答 | 2026-08-22 22:08:50]