hdu 1496 Equations hash表

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1496

思路：

• hash表，将原来\(n^{4}\)降为\(n^{2}\)
• 关系式：\(a*{x{}_1}^{2}+b*{x{}_2}^{2}=-c*{x{}_3}^{2}-d*{x{}_4}^{2}\)
• 详见hdu课件：https://wenku.baidu.com/view/af87677fa76e58fafab003e5.html

代码：

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

#define _for(i,a,b) for(int i=(a); i<(b); ++i)

#define _rep(i,a,b) for(int i=(a); i<=(b); ++i)

int ha[2000003];

int x[101],a,b,c,d,sum;

void init() {

    _rep(i,1,100) x[i]=i*i;

}

int main() {

    init();

    while(~scanf("%d %d %d %d",&a,&b,&c,&d)) {

        if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0)) {

            printf("0\n");

            continue;

        }

        memset(ha,0,sizeof(ha));

        _rep(i,1,100) _rep(j,1,100) ha[a*x[i]+b*x[j]+1000000]++;

        sum=0;

        _rep(i,1,100) _rep(j,1,100) sum+=ha[1000000-c*x[i]-d*x[j]];

        printf("%d\n", sum*16);

    }

    return 0;

}