寻找满足最大公因数条件的最小数字 C++ 实现

好的，我们来分析并解决这个问题。 ## 🧩 题意理解 题目要求找到满足以下条件的最小正整数 `c`： 1. `b` 是 `a` 和 `c` 的 **最大公因数 (GCD)**。 2. `c` 不能等于 `b`。 3. `c` 必须小于 1000。 4. 题目保证 `a > b`。 我们需要输出符合条件的 `c`。 --- ## 💡 思路推导 ### 🔍 已知条件： - `b = gcd(a, c)`，即 `b` 能整除 `a` 且 `b` 能整除 `c`。 - 因为 `gcd(a, c) = b`，意味着 `b` 是 `a` 和 `c` 的公共因子，并且 **最大** 的公共因子就是 `b` 本身。 这意味着： - `a` 和 `c` 没有比 `b` 更大的公因数。 - 换句话说，`a / b` 与 `c / b` 是互质的（`gcd` 为 1）。 所以我们可以假设： - `a = b * A` - `c = b * C` - 要求 `gcd(A, C) = 1`，并且 `C ≠ 1`（因为 `c ≠ b`），同时 `C` 最小。 并且满足： `c < 1000` → `b * C < 1000` → `C < 1000 / b`。 --- ### 🧪 解题步骤： 1. 计算 `A = a / b`。 2. 从小到大遍历可能的 `C` 值（从 2 开始，到 `(1000 / b)` 结束）： - 检查 `gcd(A, C)` 是否等于 1。 - 如果是，则 `c = b * C` 就是答案。 3. 返回找到的第一个满足条件的 `c`。 --- ## 🧑‍💻 C++ 代码实现 ```cpp #include <iostream> using namespace std; // 计算最大公因数 int gcd(int x, int y) { while (y != 0) { int temp = y; y = x % y; x = temp; } return x; } int main() { int a, b; cin >> a >> b; int A = a / b; // 化简后的因子 int limit = 1000 / b; // C 的最大可能值（保证 c < 1000） // 从最小的 C=2 开始找 for (int C = 2; C < limit; ++C) { if (gcd(A, C) == 1) { // 确保互质 int c = b * C; cout << c << endl; return 0; } } // 按题目保证，这里不会执行到 return 0; } ``` --- ## ✅ 示例验证 ### 样例 1： - 输入：`6 2` - A = 6 / 2 = 3 - limit = 1000 / 2 = 500 - C 从 2 开始： - C=2：gcd(3,2)=1 ✅ → c = 2 * 2 = 4 - 输出：`4` ✅ ### 样例 2： - 输入：`12 4` - A = 12 / 4 = 3 - limit = 1000 / 4 = 250 - C=2：gcd(3,2)=1 ✅ → c = 4 * 2 = 8 - 输出：`8` ✅ --- ## ⚠️ 注意事项 & 开发建议 1. **互质检查是核心** 如果 `gcd(A, C) ≠ 1`，那么 `b` 就不是 `a` 和 `c` 的 **最大** 公因数了，因为还有更大的公因数 `b * gcd(A, C)`。 2. **C 从 2 开始** 因为 `c ≠ b`，所以 C 不能等于 1，直接从 2 开始即可。 3. **上限 `limit` 的计算** `c < 1000` ⇒ `b * C < 1000` ⇒ `C < 1000 / b`，用整数除法确保不越界。 4. **时间复杂度和性能** 由于 `c < 1000`，且循环次数最多几百次，暴力枚举非常高效，无需优化。 5. **输入输出** 使用 `cin` 和 `cout` 即可，无需额外处理。 --- ######[AI写代码神器 | 1051点数解答 | 2026-06-12 19:57:59]