C++高效因数之和奇偶性判断：从暴力枚举到数学优化

## 📊 问题分析 我们需要计算从 m 到 n 每个数字的所有正因数之和，然后判断该和的奇偶性： - **奇数** → `Trap` - **偶数** → `Safe` 这里的关键点是**因数之和**，例如数字 6 的因数为 1, 2, 3, 6，和为 12（偶数）。 --- ## 💻 C++ 实现方案 ### 方法一：暴力计算（适合 n ≤ 1000） 最直观的方法是对于每个数字 i，从 1 到 i 遍历，找出所有因数并求和。时间复杂度 O(n²)，对于 n ≤ 1000 完全可行。 ```cpp #include <iostream> using namespace std; // 计算一个数的所有正因数之和 int sumOfDivisors(int num) { int sum = 0; for (int i = 1; i <= num; i++) { if (num % i == 0) { sum += i; } } return sum; } int main() { int m, n; cout << "请输入 m 和 n（1 ≤ m ≤ n ≤ 1000）: "; cin >> m >> n; for (int i = m; i <= n; i++) { int sum = sumOfDivisors(i); cout << i << ": 因数之和 = " << sum << " -> "; if (sum % 2 == 1) { cout << "Trap" << endl; } else { cout << "Safe" << endl; } } return 0; } ``` --- ### 方法二：优化版本（使用 sqrt 优化） 使用数学性质：对于任意数 n，其因数成对出现（除非是完全平方数，平方根只算一次），可以只遍历到 sqrt(n)。 ```cpp #include <iostream> #include <cmath> using namespace std; // 优化版：遍历到 sqrt(num) int optimizedSumOfDivisors(int num) { int sum = 1; // 1 总是因数 int sqrtNum = sqrt(num); for (int i = 2; i <= sqrtNum; i++) { if (num % i == 0) { sum += i; if (i != num / i) { // 避免平方根重复添加 sum += num / i; } } } // 特殊情况：num 本身 if (num > 1) { sum += num; } return sum; } int main() { int m, n; cout << "请输入 m 和 n: "; cin >> m >> n; for (int i = m; i <= n; i++) { int sum = optimizedSumOfDivisors(i); cout << i << ": 因数之和 = " << sum << " -> "; if (sum % 2 == 1) { cout << "Trap" << endl; } else { cout << "Safe" << endl; } } return 0; } ``` --- ### 🧠 数学优化技巧（更进一步） 实际上我们可以通过数学规律判断因数之和的奇偶性，而无需真正求和： **关键发现**：一个数的因数之和是奇数，当且仅当该数是**完全平方数**。 **证明思路**： - 对于非完全平方数，因数总是成对出现（a×b = n），每对的和 a+b 一定是偶数（因为 a 和 b 同奇偶） - 对于完全平方数，平方根只出现一次，导致总和多了一个奇数 因此最简洁的解法： ```cpp #include <iostream> #include <cmath> using namespace std; int main() { int m, n; cout << "请输入 m 和 n: "; cin >> m >> n; for (int i = m; i <= n; i++) { int root = (int)sqrt(i); bool isPerfectSquare = (root * root == i); cout << i << ": "; if (isPerfectSquare) { cout << "Trap" << endl; } else { cout << "Safe" << endl; } } return 0; } ``` --- ## 📋 代码运行示例 **输入**：`m = 1, n = 10` **输出**： ``` 1: Trap 2: Safe 3: Safe 4: Trap 5: Safe 6: Safe 7: Safe 8: Safe 9: Trap 10: Safe ``` 可以看到：1、4、9 都是完全平方数，确实触发陷阱。 --- ## 🛠️ 开发建议 1. **输入验证**：建议增加输入合法性检查，确保 1 ≤ m ≤ n ≤ 1000 2. **性能考量**：对于 n ≤ 1000，三种方法都可行；但如果扩展到更大范围，建议使用方法三（数学规律） 3. **代码风格**：使用有意义的变量名，添加必要注释，便于团队协作 4. **边界测试**：特别注意 m=1 和 n=1 的情况，以及完全平方数的边界 --- ## 🔗 扩展学习资源 - [因数与倍数的数学性质](https://zh.wikipedia.org/wiki/%E5%9B%A0%E6%95%B0) - [C++ 标准库 sqrt 函数文档](https://en.cppreference.com/w/cpp/numeric/math/sqrt) - [算法竞赛入门经典（刘汝佳）](https://book.douban.com/subject/25902502/) --- ######[AI写代码神器 | 1241点数解答 | 2026-08-23 18:25:44]