poj1840 哈希

虽然这题目我曾经在我们学校OJ上做过但是我那时候是用的暴力做的，这次我用的是哈希写的，我写这题目时候开始是在main函数里面写哈希感觉很麻烦很不清晰，然后我换用函数来写，清晰了很多，写完就AC了。用哈希存储前两项的值，然后遍历后三项再去哈希表中寻找这个值在前两项中出现的次数，加起来就OK了。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #define aabs(x) (x)>0?(x):-(x)
  5 #define mod 999983
  6 #define t(x) (x)*(x)*(x)
  7 struct node{
  8     int num;
  9     node *next;
 10     int cnt;
 11 }p[mod];
 12 int sign[mod];
 13 
 14 void hash(int res){
 15     int key;
 16     key=(aabs(res)) % mod;
 17     node *op;
 18     if(sign[key]==0){
 19         p[key].num=res;
 20         p[key].cnt++;
 21         p[key].next=NULL;
 22         sign[key]=1;
 23         return;
 24     }else if(sign[key]==1){
 25         op=&p[key];
 26         while(1){
 27             if(res==op->num){
 28                 op->cnt++;
 29                 return ;
 30             }
 31             if(op->next!=NULL){
 32                 op=op->next;
 33             }else break;
 34         }
 35     }
 36     node *tmp=(node *)malloc(sizeof(node));
 37     tmp->num=res;
 38     tmp->cnt=1;
 39     tmp->next=NULL;
 40     op->next=tmp;
 41     return;
 42 }
 43 int find_hash(int res){
 44     int cnt=0;
 45     int key=(aabs(res)) % mod;
 46     if(sign[key]==0){
 47         return 0;
 48     }else if(sign[key]==1){
 49         node *op=&p[key];
 50         while(1){
 51             if(res+op->num==0){
 52                 cnt=op->cnt;
 53             }
 54             if(op->next!=NULL){
 55                 op=op->next;
 56             }else break;
 57         }
 58     }
 59     return cnt;
 60 }
 61 
 62 
 63 void init(){
 64     memset(sign,0,sizeof(sign));
 65     for(int i=0;i<mod;++i){
 66         p[i].next=NULL;
 67         p[i].cnt=0;
 68     }
 69     return ;
 70 }
 71 
 72 int main(){
 73     int a1,a2,a3,a4,a5,x1,x2,x3,x4,x5;
 74     int i,j,key;
 75     int res,cnt;
 76     while(~scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5)){
 77         cnt=0;
 78         init();
 79         for(x1=-50;x1<=50;++x1){
 80             for(x2=-50;x2<=50;++x2){
 81                 if(x1==0||x2==0)    continue;
 82                 res=(t(x1))*a1+(t(x2))*a2;
 83                 hash(res);
 84             }
 85         }
 86         
 87         for(x3=-50;x3<=50;++x3)
 88         for(x4=-50;x4<=50;++x4)
 89         for(x5=-50;x5<=50;++x5){
 90             if(x3==0||x4==0||x5==0) continue;
 91             res=t(x3)*a3+t(x4)*a4+t(x5)*a5;
 92             cnt+=find_hash(res);
 93         }
 94         printf("%d
",cnt);
 95     }
 96     return 0;
 97 }
 98         
 99 
100 
101