求解小于n的两个连续正整数乘积的C++算法与优化

好的，我们来解决这个问题。 这个问题的核心在于理解“两个连续正整数的乘积”的数学形式，然后高效地找出所有符合条件且不超过 n 的数。 ## 1. 🧮 问题数学建模 两个连续的正整数，可以表示为 `i` 和 `i+1`，其中 `i` 是正整数（ ≥ 1）。 它们的乘积为： ``` P = i * (i + 1) ``` 我们要找所有 **P ≤ n** 的数。 注意：当 i=1 时，P=2；i=2 时，P=6；i=3 时，P=12；等等。这是一个严格的递增序列，因为随着 i 增大，乘积增长很快。 ## 2. 💡 高效算法思路 由于 n 最大是 10^6，直接枚举 i 从 1 开始，计算 i*(i+1)，直到结果超过 n 为止，这是**非常高效**的。复杂度约为 O(√n)，因为 i 最大不超过 √n。 具体步骤： 1. 初始化 i = 1 2. 计算 prod = i * (i + 1) 3. 如果 prod > n，则结束循环 4. 否则输出 prod，i 自增 1，重复步骤 2 ## 3. 🧪 边界条件与特殊值 - n = 1：没有任何连续正整数乘积 ≤ 1（因为最小是 2），所以无输出。 - n = 2：输出 2。 - n = 10^6：最多需要枚举到多少？解不等式 i*(i+1) ≤ 1e6，i 大致 ≤ 1000，循环次数很少。 ## 4. 🔧 C++ 完整代码实现 ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; // 输入 n for (int i = 1; ; ++i) { long long prod = static_cast<long long>(i) * (i + 1); if (prod > n) break; cout << prod << endl; } return 0; } ``` ### ⚙️ 代码解释 - `for (int i = 1; ; ++i)`：无限循环，在循环体内判断退出条件。 - `long long`：使用 `long long` 防止 `i*(i+1)` 在 n 接近 10^6 时潜在的整数溢出（虽然 i 最大约 1000，但使用 `long long` 是最佳实践）。 - `if (prod > n) break;`：一旦结果超出范围，立即终止循环。 - `cout << prod << endl;`：按顺序每行输出一个数。 ## 5. ⚡ 进阶优化与扩展建议 - **预处理法**：如果多次查询不同的 n，可以预先计算所有可能的乘积（从 i=1 到 √(max_n)）存储在数组中，查询时直接遍历输出符合条件的部分。这能极大减少重复计算。 - **数学性质**：注意到 i*(i+1) 总是偶数（因为连续整数必有一个偶数），所以输出结果全部为偶数。这个性质可用于快速验证结果。 - **二分查找**：如果预先存储了所有乘积，对于每次查询，可以用二分法找到最后一个 ≤ n 的数的位置，然后输出前面的所有值，时间复杂度 O(log m + 输出数量)（m为预存数组长度）。 ## 6. 📚 典型应用场景与学习建议 - **竞赛题常见**：这类问题频繁出现在编程竞赛的入门题中，用于考察数学转化与循环控制。 - **思考训练**：建议读者进一步思考如何修改算法求三个连续整数的乘积、或者两个连续奇数的乘积等变种。 - **推荐学习**： - C++ 基础语法（循环、输入输出） - 整数溢出预防 - 数学归纳法分析算法复杂度 ## 7. 🚩 开发建议 - **注重数据类型**：在涉及乘法时，一定要考虑结果是否可能超出 int 范围。C++ 中 int 通常是 32 位，最大约 2.1×10^9，对于此题够用，但使用 `long long` 更安全。 - **输出格式**：严格按题目要求，每行一个数，末尾换行。 - **代码可读性**：变量命名清晰（如 product, i），注释关键逻辑，便于他人理解。 --- ######[AI写代码神器 | 991点数解答 | 2026-06-05 21:34:41]