HDU 1496 Equations：暴力 + 哈希優化求四變量二次方程解數

題目大意

給定 a, b, c, d ∈ [-50, 50] \ {0}，求滿足 a·x₁² + b·x₂² + c·x₃² + d·x₄² = 0 的整數解個數，其中 xᵢ ∈ [-100, 100] \ {0}。

算法優化：分組哈希

直接四重循環 O(200⁴) 超時。將方程變形：

a·x₁² + b·x₂² = -(c·x₃² + d·x₄²)

左邊、右邊各自雙重循環 O(200²)，用哈希表統計左邊值的出現次數，遍歷右邊查找匹配。

關鍵細節

• xᵢ² 總為非負，但 a,b,c,d 有正負，結果可正可負
• 每個 xᵢ 正負各 100 個值，xᵢ² 相同，故每個平方值對應 2 個 xᵢ
• 四個變量共 2⁴ = 16 個符號組合，最終結果需乘 16
• 哈希表大小：最大絕對值 50 × 100² × 2 = 1,000,000，開陣列 2,000,010 足夠

AC 代碼

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

#define LL long long
int hashTable[2000010];  // 索引偏移 1000000

int main() {
    int a, b, c, d;
    while (cin >> a >> b >> c >> d) {
        // 快速剪枝：同號係數無解
        if (a > 0 && b > 0 && c > 0 && d > 0) {
            cout << 0 << endl;
            continue;
        }
        if (a < 0 && b < 0 && c < 0 && d < 0) {
            cout << 0 << endl;
            continue;
        }

        memset(hashTable, 0, sizeof(hashTable));
        LL ans = 0;

        // 左半部分：a*x1^2 + b*x2^2
        for (int x1 = 1; x1 <= 100; ++x1) {
            int v1 = a * x1 * x1;
            for (int x2 = 1; x2 <= 100; ++x2) {
                int sum = v1 + b * x2 * x2;
                hashTable[sum + 1000000]++;  // 偏移處理負數
            }
        }

        // 右半部分：-(c*x3^2 + d*x4^2)
        for (int x3 = 1; x3 <= 100; ++x3) {
            int v3 = c * x3 * x3;
            for (int x4 = 1; x4 <= 100; ++x4) {
                int sum = -(v3 + d * x4 * x4);
                ans += hashTable[sum + 1000000];
            }
        }

        // 每個平方值對應 2 個 x (正負)，4 個變量共 2^4 = 16 倍
        cout << ans * 16 << endl;
    }
    return 0;
}

樣例驗證

輸入：
1 2 3 -4
1 1 1 1

輸出：
39088
0

複雜度分析

• 時間：O(100² + 100²) = O(20,000) 每測試用例，極快
• 空間：O(2,000,010) 整數陣列 ≈ 8 MB

總結

經典「中間相遇」思想：將 4 變量方程拆分為兩個 2 變量子問題，利用哈希表交換空間換時間，從 O(n⁴) 降為 O(n²)。注意符號組合倍數與負數索引偏移處理。