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