【POJ1840】Eqs

本文主要是介绍【POJ1840】Eqs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=1840
题解：
首先可以想到最简单的五层循环暴力枚举，肯定会超时
我们可以将等式转化一下
$a_1x_1^3+ a_2x_2^3+ a_3x_3^3+ a_4x_4^3+ a_5x_5^3=0$等价于
$a_1x_1^3+ a_2x_2^3=-（a_3x_3^3+ a_4x_4^3+ a_5x_5^3）$
所以只需要分别枚举$x_1,x_2,x_3和x_4,x_5$，判断是否是相反数即可
考虑到计算出来的值可能比较大，所以将数字哈希一下，用map即可实现
复杂度$O(100^3+100^2)$，非常科学

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>using namespace std;
int a[6];
map<int,int> hash;int main()
{for(int i=1;i<=5;i++) cin>>a[i];for(int i=-50;i<=50;i++)for(int j=-50;j<=50;j++){if(i==0||j==0) continue;int tmp=i*i*i*a[1]+j*j*j*a[2];if(hash.find(tmp)!=hash.end()) hash[tmp]++;else hash[tmp]=1;   }long long ans=0;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;int tmp=-(i*i*i*a[3]+j*j*j*a[4]+k*k*k*a[5]);if(hash.find(tmp)==hash.end()) continue;ans+=hash[tmp];}printf("%lld\n",ans);return 0;       
} 

这篇关于【POJ1840】Eqs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---