【超级hash大法】HDU 1496 Equations
http://acm.hdu.edu.cn/showproblem.php?pid=1496题意：求有多少个解！！
Problem Description
Consider equations having the following form:
a*x1^2+b*x2^2+c*x3^2+d*x4^2=0
a, b, c, d are integers from the interval [-50,50] and any of them cannot be 0.
It is consider a solution a system ( x1,x2,x3,x4 ) that verifies the equation, xi
is an integer from[-100,100] and xi != 0, any i ∈{1,2,3,4}.
Determine how many solutions satisfy the given equation.
Input
The input consists of several test cases. Each test case consists of a single line containing the 4 coefficients a, b, c, d, separated by one or more blanks.
End of file.
Output
For each test case, output a single line containing the number of the solutions.
Sample Input
1 2 3 -4
1 1 1 1
Sample Output
39088
0
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <ctype.h>using namespace std;int hash;int main(){ int a, b, c, d, x1, x2, x3, x4, res; while (~scanf ("%d%d%d%d", &a, &b, &c, &d)) {if (a > 0 && b > 0 && c > 0 && d > 0 || a < 0 && b < 0 && c < 0 && d < 0) //都是同号必定无解，木有这个超时{puts ("0");continue;} memset (hash, 0, sizeof(hash)); res = 0; for (x1 = 1; x1 < 101; x1++) //hash令四重循环变成二重，复杂度大大减少for (x2 = 1; x2 < 101; x2++)hash++;for (x3 = 1; x3 < 101; x3++)for (x4 = 1; x4 < 101; x4++)res += hash[(0-(c*x3*x3+d*x4*x4))+2000000];res *= 16; //因为正负号不同不影响x平方的效果，所以直接枚举正数，最后乘以2的4次方，表示正负不同的组合 printf ("%d\n", res); } return 0;}
页:
[1]