求解多元多次方程解的个数

一 原问题链接

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

二 输入和输出

1 输入

唯一的输入行包括 5 个系数 a1、a2、a3、a4、a5，以空格分开

2 输出

单行输出满足方程的解的数量。

三 输入和输出样例

1 输入样例

37 29 41 43 47

2 输出样例

654

四 分析和设计

直接暴力破解肯定是超时的，可以将方程变化一下：将   = 0  变化为   = -（）， 这样就可以从 5 层循环变为 3 层循环。将等式左或右的值暴力枚举并存入哈希表，由于可能存在负值，所以让负值+25000000 转化为正数，并且保证数值的唯一性。再暴力枚举等式的另一边。将哈希表对应的值直接存在 ans 累加器，最后输出  ans。

五 代码

package poj1840;

import java.util.Scanner;

public class POJ1840 {
    static int maxn = 25000000 + 10;
    // 数组太大，不能用int（int型数组1677w左右），用short型数组
    static 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);
    }
}

六 测试

绿色为输入，白色为输出。