number of solutions to solve a multivariate multi-degree equation

A link to the original question

Eqs - POJ 1840 - Virtual Judgehttps://vjudge.net/problem/POJ-1840

Two Inputs and Outputs

1 input

The only input line consists of the 5 coefficients a1, a2, a3, a4, a5, separated by spaces

2 output

A single-line output of the number of solutions that satisfy the equation.

Three input and output samples

1 Input example

37 29 41 43 47

2 Sample output

654

Four Analysis and Design

Direct brute force cracking is definitely overtime, you can change the equation: = 0 changes to = -(), This will change from a 5-layer loop to a 3-layer loop.The left or right values ​​of the equation are violently enumerated and stored in the hash table. Since there may be negative values, let the negative value [phone] be converted into a positive number, and the uniqueness of the value is guaranteed.Then brute force the other side of the equation.Store the value corresponding to the hash table directly in the ans accumulator, and finally output ans.

Five codes

package poj1840;import java.util.Scanner;public class POJ1840 {static int maxn = 25000000 + 10;// The array is too large to use int (about 1677w for int array), use short arraystatic short hash[] = new short[maxn];static int a1, a2, a3, a4, a5;public static void main(String[] args) {int ans, temp;Scanner scanner = new Scanner(System.in);a1 = scanner.nextInt();a2 = scanner.nextInt();a3 = scanner.nextInt();a4 = scanner.nextInt();a5 = scanner.nextInt();ans = 0;for (int i = -50; i <= 50; i++)for (int j = -50; j <= 50; j++) {if (i == 0 || j == 0) continue;temp = (a1 * i * i * i + a2 * j * j * j) * (-1);if (temp < 0)temp = temp + maxn;hash[temp]++;}for (int i = -50; i <= 50; i++)for (int j = -50; j <= 50; j++)for (int k = -50; k <= 50; k++) {if (i == 0 || j == 0 || k == 0) continue;temp = a3 * i * i * i + a4 * j * j * j + a5 * k * k * k;if (temp < 0)temp = temp + maxn;if (hash[temp] > 0)ans = ans + hash[temp];}System.out.println(ans);}}

Six Tests

Green is input and white is output.