HDU 1496 Equations：雙向哈希化解四元二次方程計數

問題描述

給定整數 a,b,c,d ∈ [-50,50] 且均非 0。求滿足 a*x1² + b*x2² + c*x3² + d*x4² = 0 的整數解 (x1,x2,x3,x4) 個數，其中 xi ∈ [-100,100] 且 xi ≠ 0。多組輸入至 EOF。

暴力與優化

• 四重循環 O(200⁴) = 1.6e9，極其超時。
• 觀察方程可拆分：(a*x1² + b*x2²) + (c*x3² + d*x4²) = 0 → 兩部分和互為相反數。
• 預計算前兩項所有可能和及其出現次數，後兩項同理，再匹配相反數相乘累加。
• 複雜度從 O(N⁴) 降為 O(N²) ≈ 2×10⁴，極快。

哈希表設計

和的範圍：|a|,|b| ≤ 50，|x| ≤ 100 → |a*x²| ≤ 50×10⁴ = 5e5。兩項和絕對值 ≤ 1e6。
用兩個陣列 pos[1000005] 存 ≥0 的和計數，neg[1000005] 存 <0 的和計數（取絕對值作下標）。

關鍵代碼

int pos[1000005], neg[1000005];

int main() {
    int a,b,c,d;
    while (scanf("%d%d%d%d", &a,&b,&c,&d) == 4) {
        // 全同號無解優化
        if ((a>0 && b>0 && c>0 && d>0) || (a<0 && b<0 && c<0 && d<0)) {
            puts("0"); continue;
        }
        memset(pos, 0, sizeof(pos));
        memset(neg, 0, sizeof(neg));

        // 前兩項
        for (int x1 = 1; x1 <= 100; ++x1)
            for (int x2 = 1; x2 <= 100; ++x2) {
                int sum = a*x1*x1 + b*x2*x2;
                if (sum >= 0) pos[sum]++;
                else neg[-sum]++;
            }

        long long ans = 0;
        // 後兩項匹配
        for (int x3 = 1; x3 <= 100; ++x3)
            for (int x4 = 1; x4 <= 100; ++x4) {
                int sum = c*x3*x3 + d*x4*x4;
                if (sum > 0) ans += neg[sum];
                else ans += pos[-sum];
            }

        printf("%lld\n", ans * 16); // 每個 xi 可正負，2^4=16 倍
    }
    return 0;
}

關鍵細節解析

1. 正負分離存儲：避免負數下標，邏輯清晰。
2. 全同號剪枝：a,b,c,d 全正或全負時，左邊恒正/恒負，不可能為 0，直接輸出 0，避免無效計算導致超時。
3. ×16 係數：x1..x4 均可取正負，每個非零解對應 2⁴=16 個符號組合。代碼中 x1..x4 只遍歷 1..100，故最後乘 16。
4. 長整型：答案可能超 int（樣例 39088），用 long long 累加。

複雜度分析

• 時間：每測試案例 2 × 100² = 20,000 次循環，極快。
• 空間：兩個 1e6 int 陣列 ≈ 8 MB，合理。

總結

HDU 1496 是「Meet-in-the-Middle / 雙向哈希」的經典範例：將 4 變量方程拆分為兩組 2 變量，利用哈希表統計頻率匹配相反數，配合符號展開係數（×16）與同號剪枝，完美解決看似高維實則可分解的計數問題。此思想廣泛應用於 4SUM、子集和等問題。