POJ 1840——Eqs、HRBUST 1013——Eqs【哈希】_综合

题目传送门

Description

Consider equations having the following form:
a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0
The coefficients are given integers from the interval [-50,50].
It is consider a solution a system (x1, x2, x3, x4, x5) that verifies the equation, xi∈[-50,50], xi != 0, any i∈{1,2,3,4,5}.

Determine how many solutions satisfy the given equation.
Input

The only line of input contains the 5 coefficients a1, a2, a3, a4, a5, separated by blanks.

Output

The output will contain on the first line the number of the solutions for the given equation.

Sample Input

37 29 41 43 47

Sample Output

654

题意

输入 $5$ 个数 $(a1,a2,a3,a4,a5)∈[-50,50]$ ，求满足 $a1*$ $x1$ ³ $+ a2*$ $x2$ ³ $+ a3*$ $x3$ ³ $+ a4*$ $x4$ ³ $+ a5*$ $x5$ ³ $=0$ 的多项式的个数 $(x1,x2,x3,x4,x5)∈[-50,50]$ 。

题解

$5$ 层循环暴力解法时间复杂度肯定不允许，所以转换为 $a1*$ x1³ $+ a2*$ x2³ $=-( a3*$ x3³ $+ a4*$ x4³ $+ a5*$ x5³ $)$
可以看出，等式满足的上限范围是 $50*50$ ³，由于下标不能为负数，数组下标统一增大 $mid$
然后暴力水过~~~

AC-Code

#inlcude<bits/stdc++.h>
using namespace std;const int maxn = 12500000 << 1;
short h[maxn];
int main() {const int mid = 12500000;int a, b, c, d, e;while (cin >> a >> b >> c >> d >> e) {memset(h, 0, sizeof h);int ans = 0;for (int i = -50; i <= 50; ++i) {if (!i)	continue;for (int j = -50; j <= 50; ++j) {if (!j)	continue;++h[a * i * i * i + b * j * j * j + mid];}}for (int i = -50; i <= 50; ++i) {if (!i)	continue;for (int j = -50; j <= 50; ++j) {if (!j)	continue;for (int k = -50; k <= 50; ++k) {if (!k)	continue;if (-(c * i * i * i + d * j * j * j + e * k * k * k) + mid < maxnand -(c * i * i * i + d * j * j * j + e * k * k * k) + mid >= 0)ans += h[-(c * i * i * i + d * j * j * j + e * k * k * k) + mid];}}}cout << ans << endl;}return 0;
}