G1004 [GESP202306 一级] 累计相加 题解

难度：2（GeekPi教学评定）；知识点：循环累加、递推、整数运算。

解题思路

第i次累加得到1+2+…+i，再把所有这些和相加。入门写法可维护 prefix 与 total：每轮 prefix 加i，total 加prefix。参考代码使用等价公式 n(n+1)(n+2)/6。

为什么正确

将i(i+1)/2从1加到n，利用平方和与等差数列求和公式可化为n(n+1)(n+2)/6；也可由逐轮累计验证。

易错点

题意是把每个前缀和再次累计，不是只计算1到n的和；本题n≤100，整数乘积安全。

复杂度

时间：O(1)；逐轮累计写法为O(n)；额外空间：O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    cout<<n*(n+1)*(n+2)/6;
}

来源与说明

本题解为配套教学整理，非官方题解。题库使用自行生成的测试数据，6个测试点。