HDU 1496 Equations

Description

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

给出a b c d，在一定范围内找出符合上述等式的方案数

Analyze

前两项和作为一部分，遍历时hash数组记录结果，后两项和移到右边作为另一部分，遍历hash数组查找有无相同结果

数值区间决定hash空间

a、b、c、d区间对称，上限为50

x区间对称，上限为100，x * x上限为 10000

（x无需从-100开始遍历，因为需要的是x * x,所以只遍历正半轴即可，对于每一个可行的x，方案数乘2，因为有四个x（都是自变量），所以最终结果乘16 ）

a * x * x 上限为 500000，再加一个 b * x * x 上限 到达 1000000

因为a、b市对称区间，下限就到-1000000，进行坐标偏移，总共需要2000000的空间

Code

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int has[2000100];

int main()
{
    int a, b, c, d, ans;
    while(~scanf("%d%d%d%d", &a, &b, &c, &d))
    {
        if(a * b > 0 && b * c > 0 && c * d > 0)
        {
            cout << '0' << '\n';
            continue;
        }
        ans = 0;
        memset(has, 0, sizeof(has));
        for(int i = 1; i <= 100; ++i)
            for(int j = 1; j <= 100; ++j)
                has[a * i * i + b * j * j + 1000000]++;
        for(int i = 1; i <= 100; ++i)
            for(int j = 1; j <= 100; ++j)
                    ans += has[- c * i * i - d * j * j + 1000000];
        cout << ans * 16 << '\n';
    }
    return 0;
}