HDU 5053 The Sum of Cube：區間立方和預處理前綴和

問題描述

同 HDU 5053：T 組測資，每組給 [A, B] (1 ≤ A ≤ B ≤ 10000)，求 Σ i^3。輸出 Case #t: ans。

解法：前綴和 O(1) 查詢

預計算 sum[i] = Σ_{k=1}^i k^3 (i ≤ 10000)。答案 = sum[B] - sum[A-1]。
使用 long long 防溢出（10000^3 = 1e12，總和 ≈ 2.5e15）。

參考代碼

#include 
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int MAXN = 10000;
    vector pre(MAXN + 1);
    for (int i = 1; i <= MAXN; ++i) pre[i] = pre[i-1] + (ll)i * i * i;

    int T; cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        int A, B; cin >> A >> B;
        ll ans = pre[B] - pre[A-1];
        cout << "Case #" << cas << ": " << ans << '\n';
    }
    return 0;
}

關鍵細節

• (ll)i * i * i 先轉型再乘，避免 int 溢出。
• 輸出格式嚴格匹配 Case #t: ans。
• 若 B 上限更大，可用公式 (n(n+1)/2)^2 直接計算。

複雜度

預處理 O(10000)，查詢 O(1)，總時間 O(T + MAXN)。

總結

HDU 5053 是典型預處理前綴和答區間查詢題。注意 64 位整數、乘法順序、輸出格式即可輕鬆 AC。