# HDU 1496 Equations simple half enumeration + simple hash

Problem meaning: find the number of integer solutions of equation a*x1^2+b*x2^2+c*x3^2+d*x4^2=0
Note: (1) a, b, c and d are integer constants and belong to the closed range [- 50, 50]
(2) x is a nonzero integer of the closed interval [- 100100]

Idea: enumerate a*x1^2+b*x2^2 and c*x3^2+d*x4^2 respectively to save the results of the former, and enumerate the latter to make c*x3^2+d*x4^2=-a*x1^2+b*x2^2. Note that when a, B, C and d are both positive or both negative, there is no solution. This is an important pruning. Since you want to save negative numbers with subscripts, add a number uniformly to make it nonnegative.

Note: there is a pit, memset should be placed after pruning, otherwise too many case s will timeout.

Code: c++

```#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <cstring>
#include <set>
#include <stack>
#include <cstdlib>
#include <bitset>
using namespace std;

const int maxn = (int)2e6 + 100;
const int BASE = maxn / 2;

int val[maxn];

int a, b, c, d;

int main()
{
int i, j, t;
while (scanf("%d%d%d%d", &a, &b, &c, &d) != EOF)
{
if ((a > 0 && b > 0 && c > 0 && d > 0) || (a < 0 && b < 0 && c < 0 && d < 0))
{
cout << 0 << endl;
continue;
}
memset(val, 0, sizeof(val));
for (i = 1; i <= 100; i++)
{
for (j = 1; j <= 100; j++)
{
t = a * i * i + b * j * j;
val[BASE - t]++;
}
}
int ans = 0;
for (i = 1; i <= 100; i++)
{
for (j = 1; j <= 100; j++)
{
t = c * i * i + d * j * j;
ans += val[BASE + t];
}
}
cout << 16 * ans << endl;
}
return 0;
}
```

Posted on Thu, 09 Jan 2020 11:27:23 -0800 by Volitics