Equations（哈希）

刺骨的言语ヽ痛彻心扉 2022-08-01 11:17 149阅读 0赞

# Equations #

**Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 6254    Accepted Submission(s): 2531**

Problem Description

Consider equations having the following form:    
  
a\*x1^2+b\*x2^2+c\*x3^2+d\*x4^2=0  
a, b, c, d are integers from the interval \[-50,50\] and any of them cannot be 0.  
  
It is consider a solution a system ( x1,x2,x3,x4 ) that verifies the equation, xi is an integer from \[-100,100\] and xi != 0, any i ∈\{1,2,3,4\}.  
  
Determine how many solutions satisfy the given equation.

Input

The input consists of several test cases. Each test case consists of a single line containing the 4 coefficients a, b, c, d, separated by one or more blanks.  
End of file.

Output

For each test case, output a single line containing the number of the solutions.

Sample Input

1 2 3 -4
    1 1 1 1

Sample Output

39088
    0

Author

**这一题如果不使用哈希表存的话也可以三重暴力！**

**费时间**

**用哈希的话可以两个二重循环的时间复杂度！**

**特别好，记录一下！同时也说明了哈希的用处！**

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int hash1[3000050];//50*100*100*2=1000000;
    int main()
    {
        int a,b,c,d,ans,i,j;
        while(cin>>a>>b>>c>>d)
        {
            if(a>0&&b>0&&c>0&&d>0||a<0&&b<0&&c<0&&d<0)
            {
                cout<<"0"<<endl;
                continue;
            }
            ans=0;
            memset(hash1,0,sizeof(hash1));
            for(i=1;i<=100;i++)
            {
                for(j=1;j<=100;j++)
                {
                    hash1[1000000+i*i*a+j*j*b]++;
                }
            }//哈希先打表
            for(i=1;i<=100;i++)
            {
                for(j=1;j<=100;j++)
                {
                    ans+=hash1[-(i*i*c+j*j*d)+1000000];
                }
            }//比较他们的值是否相等！
            cout<<ans*16<<endl;
        }
    }