C++实现多对正整数最大公约数与最小公倍数计算

## 💡 解题思路 最大公约数（GCD）可用欧几里得算法（辗转相除法）求解，最小公倍数（LCM）通过公式 `lcm = m * n / gcd(m, n)` 计算。注意输入为 k 对正整数，需循环处理。 ## 🔧 完整代码实现 ```cpp #include <iostream> 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 k; cout << "请输入对数 k: "; cin >> k; for (int i = 0; i < k; i++) { int m, n; cout << "请输入第 " << i + 1 << " 对正整数 m 和 n: "; cin >> m >> n; // 处理输入有效性（正整数） if (m <= 0 || n <= 0) { cout << "输入必须为正整数，请重新输入！" << endl; i--; // 让当前对数重试 continue; } int g = gcd(m, n); // 注意用 long long 防止溢出，因为 m*n 可能超过 int 范围 long long lcm = (long long)m * n / g; cout << "最大公约数: " << g << ", 最小公倍数: " << lcm << endl; } return 0; } ``` ## 📝 代码说明 - `gcd` 函数使用非递归欧几里得算法，时间复杂度为 O(log(min(m, n)))。 - 最小公倍数计算时，使用 `long long` 类型避免 `m * n` 溢出（例如 m=100000, n=100000 时结果为 1e10）。 - 输入校验确保 m, n 为正整数，若非法数据则要求重新输入。 ## 🧪 示例运行 输入： ``` k = 2 (12, 18) (7, 13) ``` 输出： ``` 最大公约数: 6, 最小公倍数: 36 最大公约数: 1, 最小公倍数: 91 ``` ######[AI问答 | 521点数解答 | 2026-08-23 18:57:41]