hash直接定址 ---HDU 1496 Equations

题意：求有多少个解！！

Problem Description
Consider equations having the following form:

a*x1^2+b*x2^2+c*x3^2+d*x4^2=0

题目意思很好理解，就是求有多少种方程的解的形式，输出来就可以了。
如果用4重循环的话，可能会超时，没有试过。
直接用hash一一对应就可以了。
int hash1[10000005]保存得数是正的,a*x*x最大值就是50*100*100,再加上b*x*x就100,0000
int hash2[1000005]; //保存得数是负的

1、两重循环把s1 = a*x1*x1+b*x2*x2 (hash函数)求出来，看做第二个数组的下标，
   如果s > 0,hash1[s]++;若s <= 0; 则 hash2[-s]++;

2、然后针对另外一部分s2=c*x2*x2+d*x3*x3(hash函数),
   s1=-s2,则就是题目的一组解，而hash表记录hash1[s1]，记录符合解的个数
   所以，如果s > 0,ans+=hash2[s];若s <= 0; 则 ans+=hash1[-s];//每次是加上一组解(hash[])，
   因为数组二每次可以和一组解组合

 

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int hash1[1000005];
int hash2[1000005];

int main()
{
    int a,b,c,d;
    while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
    {
        if((a>0 && b>0 && c>0 && d>0)|| (a<0 && b<0 && c<0 && d<0))
        {
            printf("0\n");
            continue;
        }
        int ans=0;
        memset(hash1,0,sizeof(hash1));
        memset(hash2,0,sizeof(hash2));
        int i,j,s=1;
        for(i=1;i<=100;i++)
        {
            for(j=1;j<=100;j++)
            {
                s=a*i*i+b*j*j;
                if(s>0)
                    hash1[s]++;//记录这个经过hash函数映射的值的出现次数;
                else
                    hash2[-s]++;
            }
        }

        for(i=1;i<=100;i++)
        {
            for(j=1;j<=100;j++)
            {
                s=c*i*i+d*j*j;
                if(s>=0)
                    ans+=hash2[s];//将同一个s映射到hash数组，ans每次加一组
                else
                    ans+=hash1[-s];
            }
        }
        ans=ans*16;//因为是平方，所以每次的解都可以取正取负，2*2*2*2
        printf("%d\n",ans);

    }

    return 0;
}