HDU 1496 Equations （hash）

HDU 1496 Equations （hash）2014-10-06 synapse7 Equations

Time Limit: 6000/3000 MS （Java/Others）Memory Limit: 32768/32768 K （Java/Others）

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 -41 1 1 1

Sample Output

390880

Author

LLSource

“2006校园文化活动月”之“校庆杯”大学生程序设计竞赛暨杭州电子科技大学第四届大学生程序设计竞赛

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45517.htm

思路：首先，暴力会TLE，所以要把4个数分成2个和2个（关于这一点请阅读《挑战程序设计竞赛》）。注意到a*x1^2+b*x2^2的范围大小为2000000，我们不妨遍历前两个数，计算并记录在一个数组hash[]后，再遍历后两个数，并在hash[]中直接查找，这样复杂度就为O（n^2）（n=100）

完整代码：

/*187ms,8044KB*/#include<cstdio>#include<cstring>const int maxn = 1000000;int hash[2 * maxn + 5];int main（）{int a, b, c, d, i, j;long long ans;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））;for （i = 1; i <= 100; ++i）for （j = 1; j <= 100; ++j）++hash[a * i * i + b * j * j + maxn];ans = 0L;for （i = 1; i <= 100; ++i）for （j = 1; j <= 100; ++j）ans += hash[-c * i * i - d * j * j + maxn];printf（"%I64d
", ans << 4）;}}