题目大意:
对于给定的a1,a2,a3,a4,a5[-50,50]。让你求出方程a1·x1^3+a2·x2^3+a3·x3^3+a4·x4^3+a5·x5^3=0的解([-50,50]范围内)的个数。
思路:

如果只是简单地枚举范围内的所有的数,那么,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 1000000
using 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;
}