高效算法：计算1到n所有数的因子总和（C++实现）

```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; long long totalSum = 0; // 使用 long long 防止溢出 // 方法：直接计算每个数对总和的贡献 // 对于因子k，它在1到n之间出现的次数是 n/k for (int k = 1; k <= n; k++) { totalSum += (n / k) * k; // k作为因子出现的总次数乘以k } cout << totalSum << endl; return 0; } ``` ### 🔢 解题思路说明 **核心思想**：不逐个计算每个数的因子，而是统计每个数字作为因子出现的次数。 **数学原理**： - 对于任意因子 `k`（1 ≤ k ≤ n），它在区间 [1, n] 中作为因子出现的次数为 `n / k`（向下取整） - 每个 `k` 对总和的贡献为：`k × (n / k)` **示例验证**（n=5）： | 因子k | 出现次数(n/k) | 贡献值 | |-------|--------------|--------| | 1 | 5 | 5×1=5 | | 2 | 2 | 2×2=4 | | 3 | 1 | 3×1=3 | | 4 | 1 | 4×1=4 | | 5 | 1 | 5×1=5 | | 总和 | | 21 | **时间复杂度**：O(n)，空间复杂度：O(1) ######[AI问答 | 394点数解答 | 2026-06-07 19:19:11]