字符串哈希 - HDU-1496 整数哈希

题目链接：
题目大意：
题意：给出方程a(x1 ^ 2)+b(x2 ^ 2)+c(x3 ^ 2)+d(x4 ^ 2)=0的系数abcd，求共有多少组正整数解(x1, x2, x3, x4)。
a, b, c, d=[-50,50]
x1, x2, x3, x4=[-100,0）and（0， 100]

四重循环肯定T了。

因为平方有非负性，所以首先下面情况特判：

if(a<0&&b<0&&c<0&&d<0||a>0&&b>0&&c>0&&d>0)
{
    printf("0\n");
    continue;
}

我们把问题分开来：

a(x1 ^ 2)+b(x2 ^ 2) = -（ c(x3 ^ 2)+d(x4 ^ 2) ）

二重循环[1 , 100]求出所有hash = a(x1 ^ 2)+b(x2 ^ 2)的可能值。因为hash最大为 50 *10000 + 50*10000 =1000000，所以用vis标记。

再求[1 , 100] -（ c(x3 ^ 2)+d(x4 ^ 2) ）的和，与vis匹配就行了，时间复杂度O(n^2)

结果*16 因为每个x可以取得负号。 2^4=16。

#include <bits/stdc++.h>

using namespace std;
const int maxn=5000006;

int Hxz[1000010];
int Hxf[1000010];

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;
        }
        memset(Hxz, 0, sizeof(Hxz));
        memset(Hxf, 0, sizeof(Hxf));
        int s=0;
        for(int i=1;i<=100;i++)
        {
            for(int j=1;j<=100;j++)
            {
                int ans=a*i*i+b*j*j;
                if(ans>=0)
                {
                    Hxz[ans]++;
                }
                else
                {
                    Hxf[-ans]++;
                }
            }
        }
        for(int i=1;i<=100;i++)
        {
            for(int j=1;j<=100;j++)
            {
                int ans=c*i*i+d*j*j;
                if(ans>0)
                {
                    s+=Hxf[ans];
                }
                else
                {
                    s+=Hxz[-ans];
                }
            }
        }
        printf("%d\n",s*16);
    }

    return 0;
}