HDU 2132 An easy problem：前綴和預計算的 64 位整數陷阱

問題描述

定義 `sum(n)`：
`sum(i) = sum(i-1) + i³` 如果 i 能被 3 整除，
`sum(i) = sum(i-1) + i` 否則。
多組輸入 n (≤ 100,000)，n < 0 結束。輸出 `sum(n)`。

解法：預計算前綴和

遞推公式簡單，直接預計算 `f[i]` 到 100,000，查詢 O(1)。

關鍵坑點：i³ 溢出 32 位整數

`i` 最大 100,000，`i³ = 10¹⁵`，**遠超 32 位有符號整數範圍 (2.1×10⁹)**。必須用 **64 位整數**（`long long` / `__int64`）存儲 `f[]` 和中間計算 `i*i*i`。
**注意**：`i` 本身也要宣告為 64 位，否則 `i*i*i` 先按 32 位計算溢出再轉 64 位。

正確代碼

#include <cstdio>
#include <cstring>
using namespace std;

long long f[100005];

int main() {
    memset(f, 0, sizeof(f));
    f[1] = 1;
    for (long long i = 2; i <= 100000; i++) {  // i 必須是 long long
        if (i % 3 == 0) f[i] = f[i-1] + i*i*i;
        else f[i] = f[i-1] + i;
    }

    long long n;
    while (~scanf("%lld", &n) && n >= 0) {
        printf("%lld\n", f[n]);
    }
    return 0;
}

樣例驗證

輸入：1 2 3 -1
輸出：
1        (1)
3        (1+2)
30       (1+2+27)

總結

HDU 2132 看似簡單，實測**整數溢出**是唯一陷阱。預計算 + 64 位整數（包含迴圈變量）是標準解法。此類「前綴和預計算 + 大數」模式常見於 ACM 入門題（如 HDU 2030、2031 等）。