Tổng chuỗi 1 + (1+2) + (1+2+3) + ... + (1+2+...+n) trong C++

Cho n. Tính S = 1 + (1+2) + (1+2+3) + ... + (1+2+...+n).

Ví dụ

n = 4: S = 1 + 3 + 6 + 10 = 20

Quan sát

Số hạng thứ i là tổng i số tự nhiên đầu tiên: i(i+1)/2.

Tổng: S = Σ[i=1..n] i(i+1)/2 = 1/2 Σ(i² + i) = n(n+1)(n+2)/6.

(Trùng công thức tổng số tam giác bài 1003079304).

Chương trình C++

#include <iostream>
using namespace std;

long long calcSeriesSum(int n) {
    return 1LL * n * (n + 1) * (n + 2) / 6;
}

int main() {
    int n = 7;
    cout << "Tong chuoi = " << calcSeriesSum(n); // 84
    return 0;
}

Kết quả

Tong chuoi = 84

Độ phức tạp

O(1) thời gian, O(1) bộ nhớ. Cực kỳ hiệu quả.