题目链接
题目描述
帮助牛牛计算公式 Sum = Σ(i=1 to n) [i * (i+1) / 2] 的结果。
输入描述:
输入一个整数 n (1 ≤ n ≤ 10^6)。
输出描述: 输出一个整数表示公式计算结果。
解题思路
本题要求计算一个级数的和。每一项 i * (i+1) / 2 本身就是一个著名的数列，称为三角数（Triangular Number），因为它代表了构成一个等边三角形所需的点的数量。
T_i = 1 + 2 + ... + i = i * (i+1) / 2
所以，原问题等价于求前 n 个三角数之和。
思路一：直接循环 (Brute Force)
最直接的方法是使用一个循环，从 i = 1 遍历到 n。在每次迭代中，计算当前三角数 i * (i+1) / 2 的值，然后累加到一个总和变量中。
这个方法思路清晰，但由于 n 的值最大可以达到 10^6，循环 n 次在某些语言或平台上可能效率不够高，甚至有超时的风险。因此，我们应该寻找一个更高效的数学方法。
思路二：数学公式 (O(1) Solution)
对这种有规律的求和，通常存在一个封闭形式的数学公式。
我们要计算的是 S_n = Σ(i=1 to n) T_i = Σ(i=1 to n) [i * (i+1) / 2]
我们可以展开这个和式：
S_n = (1/2) * Σ(i=1 to n) (i^2 + i)
S_n = (1/2) * ( Σ(i=1 to n) i^2 + Σ(i=1 to n) i )
这里需要用到两个经典的求和公式：
- 自然数求和公式:
Σ(i=1 to n) i = n * (n+1) / 2 - 平方数求和公式:
Σ(i=1 to n) i^2 = n * (n+1) * (2n+1) / 6
将这两个公式代入：
S_n = (1/2) * [ n(n+1)(2n+1)/6 + n(n+1)/2 ]
提取公因式 n(n+1)/2:
S_n = (1/2) * [ (n(n+1)/2) * ((2n+1)/3 + 1) ]
S_n = (1/2) * [ (n(n+1)/2) * ((2n+1+3)/3) ]
S_n = (1/2) * [ (n(n+1)/2) * (2(n+2)/3) ]
S_n = n * (n+1) * (n+2) / 6
这个结果 n*(n+1)*(n+2)/6 被称为四面体数（Tetrahedral Number），它正好是前 n 个三角数的和。
这个公式只需要进行几次乘法和一次除法，时间复杂度为 O(1)，可以即时计算出结果，无论 n 有多大。
注意: n 的值可能很大，n * (n+1) * (n+2) 的结果可能会超过标准32位整数的表示范围，因此在编程时需要使用64位整数类型（如 C++ 的 long long 或 Java 的 long）来存储中间结果和最终和，以防止溢出。
代码
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
// 使用64位整数防止中间结果溢出
// n * (n + 1) * (n + 2) 必定能被 2 和 3 整除，所以也能被 6 整除
long long result = n * (n + 1) * (n + 2) / 6;
cout << result << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
// 使用 long 类型防止溢出
long result = n * (n + 1) * (n + 2) / 6;
System.out.println(result);
}
}
# 读取输入的 n
n = int(input())
# Python 的整数类型支持任意精度，不会溢出
result = n * (n + 1) * (n + 2) // 6
print(result)
算法及复杂度
- 算法：数学公式法 / 四面体数。
- 时间复杂度：
，因为计算只涉及几次算术运算，与
n的大小无关。 - 空间复杂度：
京公网安备 11010502036488号