POJ 1840 Eqs：五元三次方程求解數，哈希優化暴力枚舉

問題描述

求方程 a1·x1³ + a2·x2³ + a3·x3³ + a4·x4³ + a5·x5³ = 0 的整數解個數，其中 xi ∈ [-50, 50] \ {0}，ai ∈ [-50, 50]。直接五重循環 101⁵ ≈ 10¹⁰ 超時。

分組哈希優化：O(N³) → O(N²)

將方程重組：

(a1·x1³ + a2·x2³) = -(a3·x3³ + a4·x4³ + a5·x5³)

1. 枚舉 x1, x2（約 100² = 10⁴ 組），計算左邊值 L = -(a1·x1³ + a2·x2³)，統計頻次存入哈希表
2. 枚舉 x3, x4, x5（約 100³ = 10⁶ 組），計算右邊值 R = a3·x3³ + a4·x4³ + a5·x5³，查詢哈希表累加答案

總操作數 ~ 10⁶，極快。

關鍵實現細節

• 哈希表大小：最大絕對值 50×50³×2 ≈ 1.25e7，開陣列 2.5e7+1 直接定址（偏移量 1.25e7）
• 類型優化：用 short 存頻次（最大組合數 < 32767），節省內存提升緩存命中
• 預計算立方：cube[i] = i*i*i 避免重複乘法

C++ 代碼

#include <cstdio>
#include <cstring>
const int OFFSET = 25000000;
short hash[25000001];
int a[5], cube[101];

int main() {
    for (int i = -50; i <= 50; i++) cube[i+50] = i*i*i;
    while (scanf("%d%d%d%d%d", &a[0],&a[1],&a[2],&a[3],&a[4]) == 5) {
        memset(hash, 0, sizeof(hash));
        // 左邊兩變量
        for (int x1 = -50; x1 <= 50; x1++) if (x1)
        for (int x2 = -50; x2 <= 50; x2++) if (x2) {
            int sum = -(a[0]*cube[x1+50] + a[1]*cube[x2+50]);
            hash[sum + OFFSET]++;
        }
        // 右邊三變量
        int ans = 0;
        for (int x3 = -50; x3 <= 50; x3++) if (x3)
        for (int x4 = -50; x4 <= 50; x4++) if (x4)
        for (int x5 = -50; x5 <= 50; x5++) if (x5) {
            int sum = a[2]*cube[x3+50] + a[3]*cube[x4+50] + a[4]*cube[x5+50];
            ans += hash[sum + OFFSET];
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 時間：O(100² + 100³) ≈ 10⁶ 操作，毫秒級
• 空間：~50 MB（short[2.5e7]），符合限制

此題展示了「分組 + 哈希/定址表」化解高維枚舉的經典技巧，將指數級暴力降為多項式複雜度。