hdu 1496 Equations（非常巧妙的hash）

Equations

Time Limit: 6000/3000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1729????Accepted Submission(s): 662

#include <iostream>#include <stdio.h>#include <algorithm>#include <memory.h>using namespace std;int f1[1000005]; //保存得数是正的int f2[1000005]; //保存得数是负的int main(){ int i, j, k, sum; int a, b, c, d; while(scanf("%d %d %d %d", &a, &b, &c, &d) != EOF) { //abcd全部大于0或者小于0，肯定无解。要加上这个，不然超时 if(a>0 && b>0 && c>0 && d>0 || a<0 && b<0 && c<0 && d<0) { printf("0\n"); continue; } memset(f1, 0, sizeof(f1)); memset(f2, 0, sizeof(f2)); for(i = 1; i <= 100; i++) { for(j = 1; j<= 100; j++) { k = a*i*i + b*j*j; if(k >= 0) f1[k]++; //k>=0 f1[k]++ else f2[-k]++; //k<0 f2[k]++ } } sum = 0; for(i = 1; i <= 100; i++) { for(j = 1; j<= 100; j++) { k = c*i*i + d*j*j; if(k > 0) sum += f2[k]; //若k为正，加上的f2[k] else sum += f1[-k]; //若k为负，加上的f1[k] } } printf("%d\n", 16*sum); //每个解有正有负，结果有2^4种 } return 0;}?