这道题在a,b,c,d未知的情况下，是有200万的可能的结果，但是当a,b,c,d给定则变成2万了，当然这2万是不连续的，那么为了节省空间，可以用线性探测，数组要开的比2万大。
无线性探测代码
1 #include<cstdio>
2 #include<cstring>
3 int hash[2000001] ;
4 int hash_fun(int num){
5 return num + 1000000;
6 }
7 int main(){
8 int a,b,c,d;
9 int sq[101] ={0};
10 for(int i = 1; i <= 100; i++)
11 sq[i] = i*i;
12 while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){
13 if((a<0 && b<0 && c<0 && d<0) ||
14 (a>0 && b>0 && c>0 && d>0) ){
15 printf("0\n");
16 continue;
17 }
18 memset(hash,0,sizeof(hash));
19 for(int i = 1; i <= 100; i++)
20 for(int j = 1; j <= 100; j++)
21 hash[hash_fun(-sq[i]*a - sq[j]*b)]++;
22 int ans = 0;
23 for(int i = 1; i <= 100; i++)
24 for(int j = 1; j <= 100; j++)
25 ans += hash[hash_fun(sq[i]*c + sq[j]*d)];
26 printf("%d\n",ans*16);
27 }
28 }
29
线性探测：h(k)%S被占用，则用(h(k)+i)%S,直到找到没有被占用的，因为使用线性探测就使h(k)存在不确定性，故在h(k)处必须保存k的值，即该数组是一结构体的数组。
先说一下一段错误的代码
1 #include<cstdio>
2 #include<cstring>
3 const int maxn = 21000;
4 struct hashn{
5 int k;
6 int c;
7 };
8 hashn hash[100000] ;
9 int hash_fun(int num){
10 int t = num % maxn;
11 if(t < 0)t += maxn;
12 while(hash[t].k != 0 ){
13 if(hash[t].k == num)return t;
14 t = (t+1)%maxn;
15 if(t<0) t+= maxn;
16 }
17 hash[t].k = num;
18 return t;
19 }
20 int hash_fun2(int num){
21 int t = num % maxn;
22 if(t < 0)t += maxn;
23 while(hash[t].k != 0 ){
24 if(hash[t].k == num)return t;
25 t = (t+1)%maxn;
26 if(t<0) t+ maxn;
27 }
28 return t;
29 }
30 int main(){
31 int a,b,c,d;
32 int sq[101] ={0};
33 for(int i = 1; i <= 100; i++)
34 sq[i] = i*i;
35 while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){
36 if((a<0 && b<0 && c<0 && d<0) ||
37 (a>0 && b>0 && c>0 && d>0) ){
38 printf("0\n");
39 continue;
40 }
41 for(int i = 1; i <= 100000;i++)
42 hash[i].c = hash[i].k = 0;
43 for(int i = 1; i <= 100; i++)
44 for(int j = 1; j <= 100; j++)
45 hash[hash_fun(-sq[i]*a - sq[j]*b)].c++;
46 int ans = 0;
47 for(int i = 1; i <= 100; i++)
48 for(int j = 1; j <= 100; j++){
49 int temp = hash_fun(sq[i]*c + sq[j]*d);
50 ans += hash[temp].c;
51 }
52 printf("%d\n",ans*16);
53 }
54 }
这段代码有一个比较明显的错误，还有一个不明显但是很容易错的地方。
maxn定为21000过小了，即使数组足够大，但是这也只用到了21000。
另一个就是：
初始化hash表的时候的值在所有可能的取值中出现了！（k初始化为0）
改正后的代码：
1 #include<cstdio>
2 #include<cstring>
3 const int maxn = 51000;
4 struct hashn{
5 int k;
6 int c;
7 };
8 hashn hash[100000] ;
9 int hash_fun(int num){
10 int t = num % maxn;
11 if(t < 0)t += maxn;
12 while(hash[t].k != -1){
13 if(hash[t].k == num)return t;
14 t = (t+1)%maxn;
15 }
16 hash[t].k = num;
17 return t;
18 }
19 int main(){
20 int a,b,c,d;
21 int sq[101] ={0};
22 for(int i = 1; i <= 100; i++)
23 sq[i] = i*i;
24 while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){
25 if((a<0 && b<0 && c<0 && d<0) ||
26 (a>0 && b>0 && c>0 && d>0) ){
27 printf("0\n");
28 continue;
29 }
30 for(int i = 0; i <= 100000;i++){
31 hash[i].c = 0;
32 hash[i].k = -1;
33 }
34 for(int i = 1; i <= 100; i++)
35 for(int j = 1; j <= 100; j++)
36 hash[hash_fun(-sq[i]*a - sq[j]*b)].c++;
37 int ans = 0;
38 for(int i = 1; i <= 100; i++)
39 for(int j = 1; j <= 100; j++){
40 int temp = hash_fun(sq[i]*c + sq[j]*d);
41 ans += hash[temp].c;
42 }
43 printf("%d\n",ans*16);
44 }
45 }