杭電OJ 2007 題解：區間平方立方和——偶數平方和與奇數立方和

題目描述

輸入兩個整數 m, n（多組，EOF 結束），計算區間 [min(m,n), max(m,n)] 內：

• 所有偶數的平方和 → a
• 所有奇數的立方和 → b
• 輸出 a b

標準解法

#include 

int main(void) {
    int m, n;
    while (scanf("%d %d", &m, &n) == 2) {
        // 確保 m <= n
        if (m > n) {
            int t = m; m = n; n = t;
        }
        long long even_sq_sum = 0, odd_cu_sum = 0;
        for (int i = m; i <= n; i++) {
            if (i % 2 == 0) {
                even_sq_sum += 1LL * i * i; // 1LL 強制長長整型運算防溢出
            } else {
                odd_cu_sum += 1LL * i * i * i;
            }
        }
        printf("%lld %lld\n", even_sq_sum, odd_cu_sum);
    }
    return 0;
}

關鍵點

1. 區間標準化：交換確保 m <= n，簡化循環邊界。
2. 長長整型防溢出：i*i 或 i*i*i 易溢出 32 位 int，乘以 1LL 提升運算精度。
3. 奇偶判斷：i % 2 == 0 為偶數，!= 0 為奇數（含負數）。
4. 包含端點：循環條件 i <= n。

測試用例

優化：數學公式 O(1) 計算（大區間）

若區間極大（如 1 到 10⁹），循環超時，可用求和公式：

• 偶數平方和：4 * Σk² (k=1..n/2) = 4 * n/2 * (n/2+1) * (n+1) / 6
• 奇數立方和：Σ(2k-1)³ = 2n⁴ - n² (推導略)

但 OJ 題目通常數據範圍允許 O(n) 循環，直觀代碼優先。