首页 > ACM题库 > HDU-杭电 > HDU 1496 Equations-枚举-[解题报告] C++
2013
12-11

HDU 1496 Equations-枚举-[解题报告] C++

Equations

问题描述 :

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.

输入:

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.

输出:

For each test case, output a single line containing the number of the solutions.

样例输入:

1 2 3 -4
1 1 1 1

样例输出:

39088
0

/*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\n", ans << 4);
	}
}

解题报告转自:http://blog.csdn.net/synapse7/article/details/14554761


  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。