gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
准确的话,需要用__i64,不用也可以过
  1 #include <cstdio>
  2 
  3 const int SIZE = 101 ;
  4 const int MAXN = 14999 ;
  5 
  6 struct HashItem
  7 {
  8     int m_num ;
  9     int m_cnt ;
 10     HashItem *next ;
 11 };
 12 
 13 HashItem hash[MAXN] , g_Temp[10001] ;
 14 int g_Pos ;
 15 int ans ;
 16 
 17 //生成x的所有可能值
 18 int gArray[SIZE] ;
 19 int P3(const int& x)
 20 {
 21     return ( x * x * x ) ;
 22 }
 23 void Produce()
 24 {
 25     for ( int i = 0 , j = 0 ; i < SIZE ; ++i )
 26     {
 27         if ( i - 50 != 0 )
 28         {
 29             gArray[j++] = P3(i - 50) ;
 30         }
 31     }
 32 }
 33 
 34 void Insert( const int& num )
 35 {
 36     int tmp ;
 37     if ( num < 0 )
 38         tmp = num * -1 ;
 39     else
 40         tmp = num ;
 41     int key = tmp % MAXN ;
 42     HashItem *ptr = &hash[key] ;
 43     
 44     while ( ptr && ptr->m_cnt != 0 )
 45     {
 46         if ( ptr->m_num == num )
 47         {
 48             ptr->m_cnt++ ;
 49             return ;
 50         } 
 51         ptr = ptr->next ;
 52     }
 53     
 54     if ( hash[key].m_cnt == 0 )
 55     {
 56         hash[key].m_num = num ;
 57         hash[key].m_cnt = 1 ;
 58     }
 59     else {
 60         ptr = &g_Temp[g_Pos++] ;
 61         ptr->m_cnt = 1 ;
 62         ptr->m_num = num ;
 63         ptr->next = hash[key].next ;
 64         hash[key].next = ptr ;
 65     }
 66     
 67 }
 68 
 69 int Find( const int& num )
 70 {
 71     int tmp ;
 72     if ( num < 0 )
 73         tmp = num * -1 ;
 74     else
 75         tmp = num ;
 76     int key = tmp % MAXN ;
 77     HashItem *ptr = &hash[key] ;
 78     
 79     if ( ptr->m_cnt == 0 )
 80     {
 81         return 0 ;
 82     }
 83     
 84     while ( ptr )
 85     {
 86         if ( ptr->m_num == num )
 87         {
 88             return ptr->m_cnt ;
 89         }
 90         
 91         ptr = ptr->next ;
 92     }
 93     
 94     return 0 ;
 95 }
 96 //计算左边三个的值,并判断是否满足条件
 97 void CalLeft(const int& a, const int& b, const int& c)
 98 {
 99     int i , j , k ;
100     int num ;
101     for ( i = 0 ; i < SIZE - 1 ; ++i )
102     {
103         for ( j = 0 ; j < SIZE - 1 ; ++j )
104         {
105             for ( k = 0 ; k < SIZE - 1 ; ++k )
106             {
107                 num = gArray[i] * a + gArray[j] * b + gArray[k] * c ;
108                 num = num * -1 ;
109                 ans += Find(num) ;
110             }
111         }
112     }
113 }
114 //计算右边的值并存入hash
115 void CalRight(const int& a, const int& b)
116 {
117     int i , j ;
118     int num ;
119     
120     for ( i = 0 ; i < SIZE - 1 ; ++i )
121     {
122         for ( j = 0 ; j < SIZE - 1 ; ++j )
123         {
124             num = gArray[i] * a + gArray[j] * b ;
125             Insert(num) ;
126         }
127     }
128     
129 }
130 
131 void Init()
132 {
133     for ( int i = 0 ; i < MAXN ; ++i )
134     {
135         hash[i].next = NULL ;
136         hash[i].m_cnt = 0 ;
137     }
138     
139     g_Pos = 0 ;
140     ans = 0 ;
141 }
142 
143 int main()
144 {
145    // freopen("in", "r", stdin) ;
146     int a, b, c, d, e ;
147     
148     Produce() ;
149     
150     while ( scanf("%d%d%d%d%d", &a, &b, &c, &d, &e) != EOF )
151     {
152         Init() ;
153         //转化为 -(a + b + c) = d + e
154         CalRight( d, e ) ; 
155         CalLeft( a, b, c ) ; 
156                         
157         printf("%d\n", ans) ;
158     }
159     
160     return 0 ;
161 }
162 



posted on 2008-11-14 11:07 阅读(880) 评论(0)  编辑 收藏 引用 所属分类: Hash应用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理