ZOJ有很多与大数相关的题目,干脆写了一个比较完整的大数类一次性解决,基本思想很简单,不多解释,代码如下:
Code
1
#ifndef BIG_INTEGER
2#define BIG_INTEGER
3
4#include "assert.h"
5#include <vector>
6using namespace std;
7
8class BigInteger
9
{
10
private:
11 // char is for performance concern
12 // data is sort from lowest bit to large bit
13 // for example, 123 is store as 321
14 vector<char> value;
15 bool isMinus;
16
17 // private constructor, for inner use only
18 BigInteger(vector<char> & v, bool isMinus)
19
{
20 this->isMinus = isMinus;
21 value = v;
22
}
23
24 // remove the 0 at the front
25 void Trim()
26 {
27 vector<char>::reverse_iterator ite;
28
29 ite = value.rbegin();
30 while(value.size() > 0 && (*ite) == '0')
31 {
32 value.pop_back();
33 ite = value.rbegin();
34 }
35
36 // if no value here, it's 0
37 if(value.size() == 0)
38 value.push_back('0');
39 }
40public:
41 // Default Constructor
42 BigInteger()
43 {
44 value.push_back('0');
45 isMinus = false;
46 }
47
48 // int constructor
49 BigInteger(int val)
50 {
51 isMinus = val < 0;
52 do
53 {
54 char c = (char)(val % 10 + '0');
55 value.push_back(c);
56 if(val == 0) // if val is 0
57 break;
58 val /= 10;
59 }while(val != 0);
60 }
61
62 // string constructor
63 BigInteger(string s)
64 {
65 int length = s.length();
66 for(int i = length - 1; i >= 0; --i)
67 {
68 value.push_back(s.at(i));
69 }
70 isMinus = length > 0 && s.at(0) == '-';
71 if(isMinus)
72 // pop up the '-' sign
73 value.pop_back();
74 }
75
76 // == operator
77 bool operator==(const BigInteger & right) const
78 {
79 if(this->Length() != right.Length() || this->isMinus != right.isMinus)
80 return false;
81
82 int length = this->Length();
83 for(int i = 0; i < length; ++i)
84 {
85 if(this->operator [](i) != right[i])
86 return false;
87 }
88 return true;
89 }
90
91 // != operator
92 bool operator!=(const BigInteger & right) const
93 {
94 return !(*this == right);
95 }
96
97 // > operator
98 bool operator>(const BigInteger & right) const
99 {
100 if(!this->isMinus && right.isMinus)
101 return true;
102 else if(this->isMinus && !right.isMinus)
103 return true;
104 else
105 {
106 assert(this->isMinus == right.isMinus);
107
108 // if it's non-negative
109 if(!this->isMinus)
110 {
111 if(this->Length() > right.Length())
112 return true;
113 else if(this->Length() < right.Length())
114 return false;
115 }
116 else
117 {
118 if(this->Length() > right.Length())
119 return false;
120 else if(this->Length() < right.Length())
121 return true;
122 }
123 }
124
125 // if two numbers are the same length
126 int length = this->Length();
127 for(int i = length - 1; i >= 0; --i)
128 {
129 if(this->operator [](i) > right[i])
130 return true;
131 else if(this->operator [](i) < right[i])
132 return false;
133 }
134 assert(*this == right);
135 return false;
136 }
137
138 bool operator>=(const BigInteger & right) const
139 {
140 return *this > right || *this == right;
141 }
142
143 bool operator<(const BigInteger & right) const
144 {
145 return right > *this;
146 }
147
148 // operator +
149 // add two numbers one bit by one
150 BigInteger operator+(const BigInteger & right) const
151 {
152 bool both_minus = false;
153
154 if(right.isMinus || this->isMinus)
155 {
156 // if two numbers both are negative
157 if(right.isMinus && this->isMinus)
158 {
159 both_minus = true;
160 }
161 // if right operand is positive while left operand is negative
162 // for example, (-3) + 5
163 // delegate to 5 - 3
164 else if(!right.isMinus)
165 {
166 assert(this->isMinus == true);
167 BigInteger copy_this(*this);
168 copy_this.isMinus = false;
169 return right - copy_this;
170 }
171 // if left operand is positive while right operand is negative
172 // for example, 5 + (-3) delegate to 5 - 3
173 else
174 {
175 assert(!this->isMinus);
176 BigInteger copy_right(right);
177 copy_right.isMinus = false;
178 return this->operator -(copy_right);
179 }
180 }
181
182 // now two numbers are the same flag, both negative or both positive
183 vector<char> result;
184
185 int min_length, max_length;
186 BigInteger longer_integer;
187
188 if(this->Length() > right.Length())
189 {
190 min_length = right.Length();
191 max_length = this->Length();
192 longer_integer = *this;
193 }
194 else
195 {
196 min_length = this->Length();
197 max_length = right.Length();
198 longer_integer = right;
199 }
200
201 int temp, i, add_one = 0;
202
203 // add the result one bit by one
204 for(i = 0; i < min_length; ++i)
205 {
206 temp = this->operator [](i) + right[i] + add_one;
207
208 add_one = temp > 9 ? 1 : 0;
209 temp %= 10;
210
211 result.push_back((char)(temp + '0'));
212 }
213
214 // while we have more add_one or the left number we have to copy them
215 while(add_one || i < max_length)
216 {
217 if(i >= max_length)
218 assert(add_one == 1);
219
220 temp = i < max_length ? longer_integer[i] + add_one : add_one;
221
222 add_one = temp > 9 ? 1 : 0;
223 temp %= 10;
224
225 result.push_back((char)(temp + '0'));
226
227 ++i;
228 }
229 return BigInteger(result, both_minus);
230 }
231
232 // operator -
233 // substract it one by one
234 BigInteger operator-(const BigInteger & right) const
235 {
236 if(right.isMinus || this->isMinus)
237 {
238 // if both left & right operand are negative
239 // for example, (-5) - (-3) delegate to 3 + (-5)
240 if(this->isMinus && right.isMinus)
241 {
242 BigInteger copy_right(right);
243 copy_right.isMinus = false;
244 return copy_right + *this;
245 }
246 // if left operand is negative while right operand is positive
247 // for example, (-5) - 3, delegate to (-5) + (-3)
248 else if(!right.isMinus)
249 {
250 assert(this->isMinus);
251 BigInteger copy_right(right);
252 copy_right.isMinus = true;
253 return *this + copy_right;
254 }
255 // if left operand is positive while right operand is negative
256 // for example, 5 - (-3), delegate to 5 + 3
257 else
258 {
259 assert(!this->isMinus);
260 BigInteger copy_right(right);
261 copy_right.isMinus = false;
262 return *this + copy_right;
263 }
264 }
265
266 // now we come to M - N while both M,N are positive
267 vector<char> result;
268
269 int min_length, max_length;
270 BigInteger bigger_integer, smaller_integer;
271
272 // return 0 if they're equal :)
273 if(*this == right)
274 {
275 return BigInteger(0);
276 }
277 else if(*this > right)
278 {
279 bigger_integer = *this;
280 smaller_integer = right;
281 }
282 else if(*this < right)
283 {
284 bigger_integer = right;
285 smaller_integer = *this;
286 }
287
288 max_length = bigger_integer.Length();
289 min_length = smaller_integer.Length();
290
291 assert(max_length >= min_length);
292
293 int temp, i, borrow_one = 0;
294
295 // substract them one bit by one
296 for(i = 0; i < min_length; ++i)
297 {
298 temp = bigger_integer[i] + borrow_one - smaller_integer[i];
299
300 borrow_one = temp < 0 ? -1 : 0;
301 temp = (temp + 10) % 10;
302
303 result.push_back((char)(temp + '0'));
304 }
305
306 // while we have more bits to copy
307 while(i < max_length)
308 {
309 temp = bigger_integer[i] + borrow_one;
310
311 borrow_one = temp < 0 ? -1 : 0;
312 temp = (temp + 10) % 10;
313
314 result.push_back((char)(temp + '0'));
315
316 ++i;
317 }
318
319 // make sure we haven't got loan any more
320 assert(borrow_one == 0);
321
322 BigInteger integer = BigInteger(result, bigger_integer == right);
323 integer.Trim();
324 return integer;
325 }
326
327 // operator *
328 // Key Algorithm:
329 // C[i + j] += A[i] + b[j]
330 BigInteger operator*(const BigInteger & right) const
331 {
332 int left_length = this->Length();
333 int right_length = right.Length();
334
335 vector<int> v(left_length + right_length);
336
337 for(int i = 0; i < left_length + right_length; ++i)
338 {
339 v[i] = 0;
340 }
341
342 // calculate the result
343 for(int i = 0; i < left_length; ++i)
344 {
345 for(int j = 0; j < right_length; ++j)
346 {
347 v[i + j] += this->operator[] (i) * right[j];
348 }
349 }
350
351 // parse result base on 10
352 vector<char> result;
353 vector<int>::iterator end = v.end();
354 for(vector<int>::iterator ite = v.begin(); ite != end; ++ite)
355 {
356 result.push_back((char)((*ite) % 10 + '0'));
357
358 if(ite + 1 != end)
359 {
360 (*(ite + 1)) += (*ite) / 10;
361 }
362 else
363 {
364 assert((*ite) < 10);
365 }
366 }
367
368 BigInteger r = BigInteger(result, this->isMinus || right.isMinus);
369 r.Trim();
370 return r;
371 }
372
373 // operator /
374 // simulate the divide operation
375 BigInteger operator/(const BigInteger & right) const
376 {
377 if(right == BigInteger(0)
378 throw new exception("Divide by Zero.");
379 // specify judgement
380 if(*this < right)
381 return BigInteger(0);
382 if(*this == right)
383 return BigInteger(1);
384
385 BigInteger temp(0);
386 BigInteger TEN(10);
387 vector<char>::const_reverse_iterator end = this->value.rend();
388 vector<char>::const_reverse_iterator ite = this->value.rbegin();
389 vector<int> quotients;
390 while(ite != end)
391 {
392 temp = temp * TEN + BigInteger((int)((*ite) - '0'));
393 int quotient = 0;
394 while(temp >= right)
395 {
396 temp = temp - right;
397 ++quotient;
398 }
399 quotients.push_back(quotient);
400 ++ite;
401 }
402
403 vector<char> result;
404 vector<int>::reverse_iterator i_end = quotients.rend();
405 for(vector<int>::reverse_iterator ite = quotients.rbegin(); ite != i_end; ++ite)
406 {
407 result.push_back((char)(*ite) + '0');
408 }
409
410 BigInteger integer(result, this->isMinus || right.isMinus);
411 integer.Trim();
412 return integer;
413 }
414
415 // delegate to -,/,* operations
416 BigInteger operator%(const BigInteger & right) const
417 {
418 return *this - (*this / right * right);
419 }
420
421 // delegate to * operations
422 BigInteger Pow(int n)
423 {
424 assert(n >= 0);
425 BigInteger result(1);
426 while(n != 0 && n--)
427 {
428 result = result * *this;
429 }
430 return result;
431 }
432
433 friend ostream & operator<<(ostream & os, const BigInteger & integer)
434 {
435 vector<char>::const_reverse_iterator ite = integer.value.rbegin();
436 vector<char>::const_reverse_iterator end = integer.value.rend();
437
438 if(integer.isMinus)
439 os << "-";
440
441 for(; ite != end; ++ite)
442 {
443 os << (*ite);
444 }
445 return os;
446 }
447
448 friend istream & operator>>(istream & is, BigInteger & integer)
449 {
450 string input;
451 is >> input;
452 integer = BigInteger(input);
453 return is;
454 }
455
456 size_t Length() const
457 {
458 return value.size();
459 }
460
461 int operator[](size_t index)
462 {
463 if(index > Length())
464 throw new exception("");
465 return value[index] - '0';
466 }
467
468 int operator[](size_t index) const
469 {
470 if(index > Length())
471 throw new exception("");
472 return value[index] - '0';
473 }
474
475 // parse to int value
476 int GetIntValue() const
477 {
478 int result = 0, index = 0;
479 vector<char>::const_iterator end = value.end();
480 for(vector<char>::const_iterator ite = value.begin(); ite != end; ++ite)
481 {
482 result += ((*ite) - '0') * (int)pow((double)10, index++);
483 }
484 return result;
485 }
486
487 // parse to string
488 string GetString() const
489 {
490 string result;
491 vector<char>::const_iterator end = value.end();
492 int index = 0;
493 for(vector<char>::const_iterator ite = value.begin(); ite != end; ++ite, ++index)
494 {
495 result += *ite;
496 }
497 return result;
498 }
499
};
500
501#endif
502
503posted on 2009-03-26 21:41
肖羽思 阅读(723)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ