HDU 1496 Equations simple half enumeration + simple hash

Title: https://cn.vjudge.net/problem/HDU-1496

Problem meaning: find the number of integer solutions of equation a*x1^2+b*x2^2+c*x3^2+d*x4^2=0
Note: (1) a, b, c and d are integer constants and belong to the closed range [- 50, 50]
(2) x is a nonzero integer of the closed interval [- 100100]

Idea: enumerate a*x1^2+b*x2^2 and c*x3^2+d*x4^2 respectively to save the results of the former, and enumerate the latter to make c*x3^2+d*x4^2=-a*x1^2+b*x2^2. Note that when a, B, C and d are both positive or both negative, there is no solution. This is an important pruning. Since you want to save negative numbers with subscripts, add a number uniformly to make it nonnegative.

Note: there is a pit, memset should be placed after pruning, otherwise too many case s will timeout.

Code: c++

#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <cstring>
#include <set>
#include <stack>
#include <cstdlib>
#include <bitset>
using namespace std;

const int maxn = (int)2e6 + 100;
const int BASE = maxn / 2;

int val[maxn];

int a, b, c, d;

int main()
{
    int i, j, t;
    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))
        {
            cout << 0 << endl;
            continue;
        }
        memset(val, 0, sizeof(val));
        for (i = 1; i <= 100; i++)
        {
            for (j = 1; j <= 100; j++)
            {
                t = a * i * i + b * j * j;
                val[BASE - t]++;
            }
        }
        int ans = 0;
        for (i = 1; i <= 100; i++)
        {
            for (j = 1; j <= 100; j++)
            {
                t = c * i * i + d * j * j;
                ans += val[BASE + t];
            }
        }
        cout << 16 * ans << endl;
    }
    return 0;
}

Posted on Thu, 09 Jan 2020 11:27:23 -0800 by Volitics