1840.cpp

POJ1840求一个有5位未知数方程解的个数,hash表的经典应用

#include <iostream>

using namespace std;
#define MAXSUM 12500000
#define MAXL 20000
#define MAXH 10000
typedef struct node
{
	int k,s;
	int next;
}NODE;

NODE link[MAXL];
int hash1[MAXH],hash2[MAXH],top;
int a1,a2,a3,a4,a5;
__int64 ans;

void init()
{
    cin>>a1>>a2>>a3>>a4>>a5;
	for (int i=0 ;i<MAXH ;i++) 
     	hash1[i] = hash2[i] = -1;
    top = -1;	
}

int getI(int key)
{
    return key%MAXH;
}
    
int newNode(int key)
{
	int p;

	p = ++top;
	link[p].k = key;
	link[p].next = -1;
	link[p].s = 1;

	return p;
}

void insert(int key,int hash[])
{
	int  p,pre,q;
	int index;
	
	index = getI(key);
	p = hash[index];
	pre = -1;
	while (p!=-1 && link[p].k<key)
	{
		pre = p;
		p = link[p].next;
	}
	if (p!=-1 && link[p].k==key)
	{
		
		link[p].s++;
	}
	else
	{
		q = newNode(key);
		if (pre != -1)
		{
			link[q].next = p;
			link[pre].next = q;
		}
		else 
		{
			link[q].next = p;
			hash[index] = q;
		}
	}

}

int find(int key,int hash[])
{
	int p;
	int index;
	
	index = getI(key);
	p = hash[index];
 	while (p!=-1 && link[p].k<key) p = link[p].next;
	if (p!=-1 && link[p].k == key) return link[p].s;
	return 0;
}

void work()
{
    int key;
    __int64 zero = 0;

    ans = 0;
    for (int i=-50 ;i<=50 ;i++)
    {
        if (!i) i++;
        for (int j=-50 ;j<=50 ;j++)
        {
            if (!j) j++;
            key = a1*i*i*i+a2*j*j*j;
            if (key < 0) insert(-key,hash1);
            else if (key > 0) insert(key,hash2);
			else zero++;
        }
    }        
    for (int i=-50 ;i<=50 ;i++)
    {
        if (!i) i++;
        for (int j=-50 ;j<=50 ;j++)
        {
            if (!j) j++;
            for (int k=-50 ;k<=50 ;k++)
            {
                if (!k) k++;
                key = a3*i*i*i+a4*j*j*j+a5*k*k*k;
                if (key>MAXSUM || -key>MAXSUM) continue;
                else if (key>0) ans += find(key,hash1);
                else if (key<0) ans += find(-key,hash2);
				else ans+=zero;
            }
        }
    }     
//	cout<<ans<<endl;
	printf("%I64d\n",ans);
}
    
int main()
{
	freopen("0.txt","r",stdin);
	freopen("1.txt","w",stdout);
    init();
    work();
    return 0;
}