//把任意長度的輸入，通過散列算法，變換成固定長度的輸出
// 經(jīng)典的哈希算法 這個題目在減少復(fù)雜度的方面真的有很多的技巧值得我學(xué)習(xí)
// 因為直接存儲四項的值 有四重循環(huán)，這樣耗時很多，所以開一個滿足題意要求的數(shù)組存儲
//等式兩邊的計算值如果出現(xiàn)下標相等就說明滿足題意，同時起到了計數(shù)的作用
//因為平方的作用從 1 -- 100 循環(huán)減少了復(fù)雜度 ，只是記得最后一定要乘以一個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 ]; //如果出現(xiàn)了相同的hash值 則：+ 1
}
}
printf ("%d\n", 16 * count); //反之count會 = 0
}
//system ("pause");
return 0;
}
posted on 2010-08-28 21:16
雪黛依夢 閱讀(471)
評論(0) 編輯 收藏 引用 所屬分類:
哈希法