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

 

题意：

给你a,b,c,d这4个数的值，然后问a*x1^2 + b*x2^2 +  c*x3^2 + d*x4^2 = 0的（x1,x2,x3,x4）解一共有多少种

思路：

第一种——>构建哈希表，优化暴力求解方程；

#include<stdio.h>
#include<string.h>
#include<algorithm>
typedef long long ll;
const ll N=2e6+10;
using namespace std;
int ha[N],p[110];
int main()
{
    int a,b,c,d;
    for(int i=1; i<101; i++)
        p[i]=i*i;
    while(~scanf("%d %d %d %d",&a,&b,&c,&d))
    {
        memset(ha,0,sizeof(ha));
        if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0))///全正全负都排除，剪枝
        {
            printf("0\n");
            continue;
        }
        for(int i=1; i<101; i++)
            for(int j=1; j<101; j++)
                ha[a*p[i]+b*p[j]+1000000]++;
        int sum=0;
        for(int i=1; i<101; i++)
            for(int j=1; j<101; j++)
                sum+=ha[-c*p[i]-d*p[j]+1000000];
        printf("%d\n",sum*16);///每个数都可正可负   16中情况
    }
    return 0;
}

第二种——>分开两部分求和，若两部分的和是0，则就相加那么多种，最后乘以16。这样就能从n^4（4层for循环）变成2*n^2（2层for循环）；

#include<stdio.h>
#include<string.h>
#include<algorithm>
typedef long long ll;
const ll N=1e6+10;
using namespace std;
int z[N],f[N];///正   负
int main()
{
    int a,b,c,d;
    while(~scanf("%d %d %d %d",&a,&b,&c,&d))
    {
        memset(z,0,sizeof(z));
        memset(f,0,sizeof(f));
        if((a<0&&b<0&&c<0&&d<0)||(a>0&&b>0&&c>0&&d>0))///全正全负肯定无解
        {
            printf("0\n");
            continue;
        }
        for(int i=1; i<101; i++)
            for(int j=1; j<101; j++)
            {
                int k=a*i*i+b*j*j;
                if(k>=0)z[k]++;///k=0也要考虑在内    因为a,b可能一正一负相加最后为0；
                if(k<0)f[-k]++;
            }
        int sum=0;
        for(int i=1; i<101; i++)
            for(int j=1; j<101; j++)
            {
                int k=c*i*i+d*j*j;
                if(k<=0)sum+=z[-k];///！
                if(k>0)sum+=f[k];
            }
        printf("%d\n",sum*16);///16理由同上  （2^4=16）;
    }
    return 0;
}

附图：

↖(^ω^)↗

~\(≧▽≦)/~啦啦啦

在我想东想西或者什么都不想的时候。等待的车，等待的人，就这样飞驰而去。

想一千次，不如去做一次。华丽的跌倒，胜过无谓的徘徊。

再长的路，一步步也能走完；再短的路，不迈开双脚也无法到达。只要想到人生那么长，外面的世界那么精彩，我就想去看看。我的努力是想去体验一个更大的世界，我不想停下我追求生命意义的脚步。希望我们成长的速度，比父母老去的速度快一些。这大概就是我们努力的意义吧。

赖床舒服，但可能迟到；熬夜很爽，但伤身体；玩手机有趣，可你也许会发现，时间流逝，你却没有进步。人要明白，越努力，越幸运，自律的程度，决定人生的高度。

愿所有不满都化为将来成功的动力。