poj 1840 : Eqs (hash)

  题意：对于方程：a1x1³+ a2x2³+ a3x3³+ a4x4³+ a5x5³=0 ，有xi∈[-50,50], xi != 0, any i∈{1,2,3,4,5}. 现在给出a1,a2,a3,a4,a5的值，求出满足上面方程的解有多少个。

  思路：hash的应用。暴力枚举的话会达到100^5，明显会超时。所以将方程分成a1x1³+ a2x2³ 和 -（a3x3³+a4x4³+ a5x5³ ）两部分，若这两部分相等，则为方程的一个解。

 

一开始以为hash的优化效果不会很明显，因为觉得代码的大部分时间会消耗在o(100^3)求方程后部分的值上，后来看了别人的解题报告，发现用hash进行优化的效果还是很恐怖的，这么说代码的大部分时间是消耗在前后两部份的排序和匹对求解的个数上，所以干脆用直接寻址表进行了优化，结果运行时间由1329MS 到了 157MS，不是一般的快。

#include <iostream>
using namespace std;
#define mq 100007
int a[100008][10];
int top[100008];
int main()
{
	int a1,a2,a3,a4,a5,t,sum=0,p,i;
	int x1,x2,x3,x4,x5;
	cin>>a1>>a2>>a3>>a4>>a5;
	for(x1=-50;x1<=50;x1++)
	{
		if(!x1)
			continue;
		for(x2=-50;x2<=50;x2++)
		{
			if(!x2)
				continue;
			t=a1*x1*x1*x1+a2*x2*x2*x2;
			p=t;
			t%=mq;
			if(t<0)
				t+=mq;
			a[t][top[t]++]=p;
		}
	}
	for(x3=-50;x3<=50;x3++)
	{
		if(!x3)
			continue;
		for(x4=-50;x4<=50;x4++)
		{
			if(!x4)
				continue;
			for(x5=-50;x5<=50;x5++)
			{
				if(!x5)
					continue;
				t=-(a3*x3*x3*x3+a4*x4*x4*x4+a5*x5*x5*x5);
				p=t;
				t%=mq;
				if(t<=0)
					t+=mq;
				for(i=0;i<top[t];i++)
					if(a[t][i]==p)
						sum++;
			}
		}
	}
	cout<<sum<<endl;
	return 0;
 }

 

 

关于hash的解法未完待续……