求解多元多次方程解的個數

一 原問題連結

Eqs - POJ 1840 - Virtual Judge

https://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);
    }
}
           

六 測試

綠色為輸入，白色為輸出。