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


    一 原问题链接

    二 输入和输出

    1 输入

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

    2 输出

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

    三 输入和输出样例

    1 输入样例

    37 29 41 43 47

    2 输出样例

    654

    四 分析和设计

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

    五 代码

    1. package poj1840;
    2. import java.util.Scanner;
    3. public class POJ1840 {
    4. static int maxn = 25000000 + 10;
    5. // 数组太大,不能用int(int型数组1677w左右),用short型数组
    6. static short hash[] = new short[maxn];
    7. static int a1, a2, a3, a4, a5;
    8. public static void main(String[] args) {
    9. int ans, temp;
    10. Scanner scanner = new Scanner(System.in);
    11. a1 = scanner.nextInt();
    12. a2 = scanner.nextInt();
    13. a3 = scanner.nextInt();
    14. a4 = scanner.nextInt();
    15. a5 = scanner.nextInt();
    16. ans = 0;
    17. for (int i = -50; i <= 50; i++)
    18. for (int j = -50; j <= 50; j++) {
    19. if (i == 0 || j == 0) continue;
    20. temp = (a1 * i * i * i + a2 * j * j * j) * (-1);
    21. if (temp < 0)
    22. temp = temp + maxn;
    23. hash[temp]++;
    24. }
    25. for (int i = -50; i <= 50; i++)
    26. for (int j = -50; j <= 50; j++)
    27. for (int k = -50; k <= 50; k++) {
    28. if (i == 0 || j == 0 || k == 0) continue;
    29. temp = a3 * i * i * i + a4 * j * j * j + a5 * k * k * k;
    30. if (temp < 0)
    31. temp = temp + maxn;
    32. if (hash[temp] > 0)
    33. ans = ans + hash[temp];
    34. }
    35. System.out.println(ans);
    36. }
    37. }

    六 测试

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

     

  • 相关阅读:
    测试人员Bug书写规范
    蓝桥云课--1014 第 1 场算法双周赛
    Java基础知识回顾
    PAT 1164 Good in C 测试点3,4
    solidworls视图与模型及绘图操作快捷方式
    STM32 PA15/JTDI 用作普通IO,烧录口不能使用问题解决
    供应链和物流的自动化新时代
    系统架构设计——互联网金融的架构设计
    js,jquery,vue设置html标签隐藏不显示
    【数据结构】二叉树
  • 原文地址:https://blog.csdn.net/chengqiuming/article/details/126081701