OJ題解：自然數的和之和 - 三角數列求和

題目數學模型

求 S = Σᵢ₌₁ᴺ Σⱼ₌₁ⁱ j = Σᵢ₌₁ᴺ i(i+1)/2 = N(N+1)(N+2)/6

即前 N 個三角數之和（四面體數）。

三種實作比較

優化版：閉合公式

#include <stdio.h>

int main() {
    int T, N;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        // 用 long long 防止中間溢位 (N≤200 時 int 足夠，但習慣用長整型)
        long long ans = 1LL * N * (N + 1) * (N + 2) / 6;
        printf("%lld\n", ans);
    }
    return 0;
}

驗證

N=1:  1*2*3/6 = 1      ✓
N=200: 200*201*202/6 = 1,353,400  ✓

數學推導

Σ i(i+1)/2 = ½ Σ(i²+i) = ½ [N(N+1)(2N+1)/6 + N(N+1)/2]
          = N(N+1)/12 [2N+1 + 3] = N(N+1)(N+2)/6