枚举法找连续正整数乘积——C++高效实现

好的，我们来一起解决这个问题。我先帮你分析一下题目要求，然后给出高效的C++实现。 ## 🔍 问题分析 题目要求：找出所有 **小于等于 n** 的正整数，这些数可以表示成 **两个连续正整数的乘积**。 ### 数学抽象 两个连续正整数的乘积可以表示为： ``` x * (x + 1) ``` 其中 `x` 是一个正整数（`x ≥ 1`）。 我们要找的是所有满足 `x*(x+1) ≤ n` 的数，并且按从小到大的顺序输出。 ### 🧮 等价公式 `x*(x+1)` 显然会随着 `x` 增大而快速增大，且是严格递增的序列： - x=1 → 1×2 = 2 - x=2 → 2×3 = 6 - x=3 → 3×4 = 12 - x=4 → 4×5 = 20 - ... 在 n ≤ 10^6 时，x 不会特别大，因为当 x ≈ 1000 时，`1000×1001 = 1,001,000` 已经超过 10^6。 ### 方法比较 | 方法 | 思路 | 时间复杂度 | 适用性 | |------|------|------------|--------| | 暴力枚举 x | 从 x=1 开始枚举，直到 x(x+1) > n | O(√n) | ✅ 最优解 | | 遍历所有数并判断 | 遍历 1..n，判断是否能写成 x(x+1) 形式 | O(n√n) | ❌ 太慢 | 显然，**直接枚举 x** 是最简单高效的方法。 --- ## 💻 代码实现（C++） ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; // 枚举连续正整数对的第一个数 x for (int x = 1; ; x++) { long long product = 1LL * x * (x + 1); // 防止乘法溢出 if (product > n) break; // 超出范围，结束 cout << product << endl; } return 0; } ``` ### 代码解释 1. **`long long product = 1LL * x * (x + 1);`** - 使用 `1LL` 将乘法提升到 long long 范围，避免 `int` 溢出（虽然 n ≤ 10^6 时 int 也够，但这是好习惯）。 2. **`if (product > n) break;`** - 因为 x(x+1) 是严格递增的，所以一旦超过 n，后续更大 x 的值必然超过 n，直接退出循环。 3. **输出顺序** - 由于 x 从小到大枚举，得到的乘积自然也是从小到大，无需再排序。 --- ## 🧪 示例测试 ### 输入 ``` 30 ``` ### 输出 ``` 2 6 12 20 30 ``` **验证**： - 2 = 1×2 - 6 = 2×3 - 12 = 3×4 - 20 = 4×5 - 30 = 5×6 ✓ --- ## 🚀 时间复杂度与空间复杂度 - **时间复杂度**：O(√n)，因为最大 x 约等于 √n。 - **空间复杂度**：O(1)，只使用了常数个变量。 对于 n=10^6，最多只需要循环约 1000 次，非常快。 --- ## ⚠️ 常见陷阱与建议 1. **忽略乘法溢出** - 虽然本例中 n 较小，但若 n 范围扩大到 10^9 或更大，`int` 乘法就可能溢出。**最好总是使用 `long long`**。 2. **不要用“遍历所有数并判断”的方法** - 错误做法：对于每个 i 从 1 到 n，判断是否存在 x 使 x(x+1)=i。这会使复杂度变为 O(n√n)，当 n=10^6 时也能跑，但如果 n 更大就会超时。**直接枚举 x 才是正解**。 3. **注意题目范围** - 题目说 1 ≤ n ≤ 10^6，但输出时最小结果是 2（因为 1×2=2），所以如果 n=1，程序不会输出任何内容，这是正确的。 --- ## 📘 相关技术栈推荐 - **数学基础**：了解连续整数乘积与二次方程的基本关系。 - **C++ 基础**：掌握 `long long`、循环、输入输出流。 - **算法思想**：枚举法（暴力搜索）的应用与优化。 --- ## 🔗 学习资源 - [C++ 官方文档 - 基本类型](https://en.cppreference.com/w/cpp/language/types) - [OI Wiki - 枚举](https://oi-wiki.org/basic/enumerate/) - [LeetCode - 连续整数乘积相关题目](https://leetcode.com/problemset/all/?search=consecutive) 如果你还有其他问题（如扩展到更大数据范围、使用其他语言实现、或更复杂的数学推导），欢迎继续提问！ ######[AI写代码神器 | 1160点数解答 | 2026-06-05 21:36:05]