//把任意长度的输入，通过散列算法，变换成固定长度的输出
// 经典的哈希算法 这个题目在减少复杂度的方面真的有很多的技巧值得我学习
// 因为直接存储四项的值 有四重循环，这样耗时很多，所以开一个满足题意要求的数组存储
//等式两边的计算值如果出现下标相等就说明满足题意，同时起到了计数的作用
//因为平方的作用从 1 -- 100 循环减少了复杂度 ，只是记得最后一定要乘以一个16哦！
#include <iostream>
#include <string>
using namespace std;
int hash[2000010];
int main ()
{
int a, b, c, d;
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 ))
{
printf ("0\n");
continue;
}
memset ( hash, 0, sizeof (hash) );
int count = 0;
for ( int i = 1; i <= 100; i ++ )
{
for ( int j = 1; j <= 100; j ++ )
{
hash[ a * i * i + b * j * j + 1000000 ] ++; //每一个不同的a*x1^2 + b*x2^2 hash值都是 1
}
}
for ( int i = 1; i <= 100; i ++ )
{
for ( int j = 1; j <= 100; j ++ )
{
count += hash[ 1000000 - c * i * i - d * j * j ]; //如果出现了相同的hash值 则：+ 1
}
}
printf ("%d\n", 16 * count); //反之count会 = 0
}
//system ("pause");
return 0;
}
posted on 2010-08-28 21:16
雪黛依梦 阅读(456)
评论(0) 编辑 收藏 引用 所属分类:
哈希法