这道题是求四元二次方程的给定范围内的整数解的个数。
最初是想暴利枚举x1, x2, x3, 的值,但是害怕超时,因为这样 的话要循环1000000次。网上搜了一下其他人的代码,居然可以用哈希求解。于是豁然开朗了。
注意剪去abcd同号的情况,不然会超时。
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int Max = 1000000;
int myHash[Max*2+10];
int main()
{
int a, b, c, d, cnt;
while(scanf("%d%d%d%d", &a, &b, &c, &d) != EOF)
{
//a,b,c,d同号时必然无解,没有剪去这个条件,就会超时。。。。
if((a > 0 && b > 0 && c > 0 && d > 0) || (a < 0 && b < 0 && c < 0 && d < 0) )
{
printf("0\n", cnt);
continue;
}
memset(myHash, 0, sizeof(myHash));
cnt = 0;
for(int x1=1; x1<=100; x1++)
for(int x2=1; x2<=100; x2++)
{
myHash[Max + a*x1*x1 + b*x2*x2] ++;
}
for(int x3=1; x3<=100; x3++)
for(int x4=1; x4<=100; x4++)
{
cnt += myHash[Max - c*x3*x3 - d*x4*x4];
}
cnt *= 16;
printf("%d\n", cnt);
}
system("pause");
return 0;
}