题目描述
考虑具有以下形式的方程：
a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0
系数被赋予区间 [-50,50] 中的整数。
考虑一个解一个系统 (x1, x2, x3, x4, x5) 来验证方程，xi∈[-50,50], xi != 0, any i∈{1,2,3,4,5 }.
确定有多少解满足给定的方程。
输入
输入的唯一一行包含 5 个系数 a1、a2、a3、a4、a5，以空格分隔。
输出
输出将在第一行包含给定方程的解数。
样本输入
37 29 41 43 47
样本输出
654
思路分析:直接暴力必定超时,我们可以对方程进行变形.
这样100^5的复杂度就变成了100 ^3 + 100 ^ 2.
然后将等式从左或右的值枚举存入哈希表,由于可能存在负值我们让负值+25000000转为正数,并且保证数值的唯一性.之后再暴力枚举另一边,将哈希表对应的值存入ans进行累加,最后得到ans的值.
并且25000000数组很大,int不可以,short足够,并且要定义成全局.
AC代码
//POJ1840 #include<iostream> #include<string.h> using namespace std; const int maxsize = 25000000+10;// short hashTab[maxsize]; int a1,a2,a3,a4,a5,ans,temp; int main() { while(cin>>a1>>a2>>a3>>a4>>a5){ ans = 0; memset(hashTab,0,sizeof(hashTab)); for(int x1 = -50;x1<=50;x1++){ for(int x2 = -50;x2<=50;x2++){ if(x1==0||x2==0){ continue; } temp = (a1*x1*x1*x1+a2*x2*x2*x2)*(-1); if(temp < 0){ temp += maxsize; } hashTab[temp]++; } } for(int x3 = -50;x3<=50;x3++){ for(int x4 = -50;x4<=50;x4++){ for(int x5 = -50;x5<=50;x5++){ if(x3==0||x4==0||x5==0){ continue; } temp = a3*x3*x3*x3+a4*x4*x4*x4+a5*x5*x5*x5; if(temp < 0){ temp += maxsize; } ans += hashTab[temp]; } } } cout<<ans<<endl; } return 0; }
