POJ - 1840 Eqs解题报告

如果只是简单地枚举范围内的所有的数，那么，100^5=10^10肯定是超时了。优化方法：用列表法首先写出x^3的所有可能值(100个)，再求出所有a1·x1^3 + a2·x2^3+ a3·x3^3的可能值（n^3）,并排序(n^3)*(log(n^3))。和所有a4·x4^3+ a5·x5^3的可能值（n^2），然后枚举所有a4·x4^3+ a5·x5^3的可能值，二分查找a1·x1^3 + a2·x2^3+ a3·x3^3的可能值中是否存在对应解(n^2)*(log(n^3))。

总时间复杂度为：(n^3)(log(n^3))。

然后写到一半发现，二分还是慢，哈希表更快，而且不需要排序，只需要O(n^3)。

#include<iostream>#include<string.h>#include<algorithm>#include<math.h>#define N 110#define MOD 1000000using namespace std;int a[6]={0};int x[N]={0};int s[N*N*N]={0};int hash[N*N*N]={0};int next[N*N*N]={0};/*int find(int x){	int ss=0;	for(int i=0;i<=MOD;i++)	{		if(x==s[i])ss++;	}	return ss;}*/int my_find(int x){	int u=(((long long)x*(long long)x)%MOD)+1;	u=hash[u];	int z=0;	while(u)	{		if(s[u]==x)		{			z++;		}		u=next[u];	}	return z;}void ceshi(){	for(int i=0;i<1000000;i++)	{		cout<<hash[i]<<" ";	}}int main(){	int n=0;	for(int i=-50;i<=50;i++)	{		if(i==0)continue;		x[n]=i*i*i;		n++;	}	for(int i=1;i<=5;i++)cin>>a[i];	int l=1;	for(int i=0;i<n;i++)	{		for(int j=0;j<n;j++)		{			for(int k=0;k<n;k++)			{								int v=0;				s[l]=a[1]*x[i]+a[2]*x[j]+a[3]*x[k];				v=((long long)s[l]*(long long)s[l])%MOD+1;				next[l]=hash[v];				hash[v]=l;				l++;			}		}	}	int sum=0;	for(int i=0;i<n;i++)	{		for(int j=0;j<n;j++)		{			int t=a[4]*x[i]+a[5]*x[j];			sum=sum+my_find(-t);//在s数组中查找是否有-t.		}	}	//ceshi();	cout<<sum;}