SHOW:
|
|
- or go back to the newest paste.
1 | #include <vector> | |
2 | #include <string> | |
3 | #include <ostream> | |
4 | #include <iomanip> | |
5 | #include <sstream> | |
6 | ||
7 | class big_integer { | |
8 | // основание системы счисления (1 000 000 000) | |
9 | static const int BASE = 1000000000; | |
10 | ||
11 | // внутреннее хранилище числа | |
12 | std::vector<int> _digits; | |
13 | ||
14 | // знак числа | |
15 | bool _is_negative; | |
16 | ||
17 | void _remove_leading_zeros(); | |
18 | void _shift_right(); | |
19 | ||
20 | public: | |
21 | // класс-исключение, бросаемое при делении на ноль | |
22 | class divide_by_zero: public std::exception { }; | |
23 | ||
24 | big_integer(); | |
25 | big_integer(std::string); | |
26 | big_integer(signed char); | |
27 | big_integer(unsigned char); | |
28 | big_integer(signed short); | |
29 | big_integer(unsigned short); | |
30 | big_integer(signed int); | |
31 | big_integer(unsigned int); | |
32 | big_integer(signed long); | |
33 | big_integer(unsigned long); | |
34 | big_integer(signed long long); | |
35 | big_integer(unsigned long long); | |
36 | ||
37 | friend std::ostream& operator <<(std::ostream&, const big_integer&); | |
38 | operator std::string() const; | |
39 | const big_integer operator +() const; | |
40 | const big_integer operator -() const; | |
41 | const big_integer operator ++(); | |
42 | const big_integer operator ++(int); | |
43 | const big_integer operator --(); | |
44 | const big_integer operator --(int); | |
45 | friend bool operator ==(const big_integer&, const big_integer&); | |
46 | friend bool operator <(const big_integer&, const big_integer&); | |
47 | friend bool operator !=(const big_integer&, const big_integer&); | |
48 | friend bool operator <=(const big_integer&, const big_integer&); | |
49 | friend bool operator >(const big_integer&, const big_integer&); | |
50 | friend bool operator >=(const big_integer&, const big_integer&); | |
51 | friend const big_integer operator +(big_integer, const big_integer&); | |
52 | big_integer& operator +=(const big_integer&); | |
53 | friend const big_integer operator -(big_integer, const big_integer&); | |
54 | big_integer& operator -=(const big_integer&); | |
55 | friend const big_integer operator *(const big_integer&, const big_integer&); | |
56 | big_integer& operator *=(const big_integer&); | |
57 | friend const big_integer operator /(const big_integer&, const big_integer&); | |
58 | big_integer& operator /=(const big_integer&); | |
59 | friend const big_integer operator %(const big_integer&, const big_integer&); | |
60 | big_integer& operator %=(const big_integer&); | |
61 | ||
62 | bool odd() const; | |
63 | bool even() const; | |
64 | const big_integer pow(big_integer) const; | |
65 | }; | |
66 | ||
67 | // создает длинное целое число со значением 0 | |
68 | big_integer::big_integer() { | |
69 | this->_is_negative = false; | |
70 | } | |
71 | ||
72 | // создает длинное целое число из C++-строки | |
73 | big_integer::big_integer(std::string str) { | |
74 | if (str.length() == 0) { | |
75 | this->_is_negative = false; | |
76 | } | |
77 | else { | |
78 | if (str[0] == '-') { | |
79 | str = str.substr(1); | |
80 | this->_is_negative = true; | |
81 | } | |
82 | else { | |
83 | this->_is_negative = false; | |
84 | } | |
85 | ||
86 | for (long long i = str.length(); i > 0; i -= 9) { | |
87 | if (i < 9) | |
88 | this->_digits.push_back(atoi(str.substr(0, i).c_str())); | |
89 | else | |
90 | this->_digits.push_back(atoi(str.substr(i - 9, 9).c_str())); | |
91 | } | |
92 | ||
93 | this->_remove_leading_zeros(); | |
94 | } | |
95 | } | |
96 | ||
97 | // удаляет ведущие нули | |
98 | void big_integer::_remove_leading_zeros() { | |
99 | while (this->_digits.size() > 1 && this->_digits.back() == 0) { | |
100 | this->_digits.pop_back(); | |
101 | } | |
102 | ||
103 | if (this->_digits.size() == 1 && this->_digits[0] == 0) this->_is_negative = false; | |
104 | } | |
105 | ||
106 | // печатает число в поток вывода | |
107 | std::ostream& operator <<(std::ostream& os, const big_integer& bi) { | |
108 | if (bi._digits.empty()) os << 0; | |
109 | else { | |
110 | if (bi._is_negative) os << '-'; | |
111 | os << bi._digits.back(); | |
112 | char old_fill = os.fill('0'); | |
113 | for (long long i = static_cast<long long>(bi._digits.size()) - 2; i >= 0; --i) os << std::setw(9) << bi._digits[i]; | |
114 | os.fill(old_fill); | |
115 | } | |
116 | ||
117 | return os; | |
118 | } | |
119 | ||
120 | // сравнивает два числа на равенство | |
121 | bool operator ==(const big_integer& left, const big_integer& right) { | |
122 | if (left._is_negative != right._is_negative) return false; | |
123 | if (left._digits.empty()) { | |
124 | if (right._digits.empty() || (right._digits.size() == 1 && right._digits[0] == 0)) return true; | |
125 | else return false; | |
126 | } | |
127 | ||
128 | if (right._digits.empty()) { | |
129 | if (left._digits.size() == 1 && left._digits[0] == 0) return true; | |
130 | else return false; | |
131 | } | |
132 | ||
133 | if (left._digits.size() != right._digits.size()) return false; | |
134 | for (size_t i = 0; i < left._digits.size(); ++i) if (left._digits[i] != right._digits[i]) return false; | |
135 | ||
136 | return true; | |
137 | } | |
138 | ||
139 | // возвращает копию переданного числа | |
140 | const big_integer big_integer::operator +() const { | |
141 | return big_integer(*this); | |
142 | } | |
143 | ||
144 | // возвращает переданное число с другим знаком | |
145 | const big_integer big_integer::operator -() const { | |
146 | big_integer copy(*this); | |
147 | copy._is_negative = !copy._is_negative; | |
148 | return copy; | |
149 | } | |
150 | ||
151 | // проверяет, является ли левый операнд меньше правого | |
152 | bool operator <(const big_integer& left, const big_integer& right) { | |
153 | if (left == right) return false; | |
154 | if (left._is_negative) { | |
155 | if (right._is_negative) return ((-right) < (-left)); | |
156 | else return true; | |
157 | } | |
158 | else if (right._is_negative) return false; | |
159 | else { | |
160 | if (left._digits.size() != right._digits.size()) { | |
161 | return left._digits.size() < right._digits.size(); | |
162 | } | |
163 | else { | |
164 | for (long long i = left._digits.size() - 1; i >= 0; --i) { | |
165 | if (left._digits[i] != right._digits[i]) return left._digits[i] < right._digits[i]; | |
166 | } | |
167 | ||
168 | return false; | |
169 | } | |
170 | } | |
171 | } | |
172 | ||
173 | // сравнивает два числа на неравенство | |
174 | bool operator !=(const big_integer& left, const big_integer& right) { | |
175 | return !(left == right); | |
176 | } | |
177 | ||
178 | // проверяет, является ли левый операнд меньше либо равен правого | |
179 | bool operator <=(const big_integer& left, const big_integer& right) { | |
180 | return (left < right || left == right); | |
181 | } | |
182 | ||
183 | // проверяет, является ли левый операнд больше правого | |
184 | bool operator >(const big_integer& left, const big_integer& right) { | |
185 | return !(left <= right); | |
186 | } | |
187 | ||
188 | // проверяет, является ли левый операнд больше либо равен правого | |
189 | bool operator >=(const big_integer& left, const big_integer& right) { | |
190 | return !(left < right); | |
191 | } | |
192 | ||
193 | // складывает два числа | |
194 | const big_integer operator +(big_integer left, const big_integer& right) { | |
195 | if (left._is_negative) { | |
196 | if (right._is_negative) return -(-left + (-right)); | |
197 | else return right - (-left); | |
198 | } | |
199 | else if (right._is_negative) return left - (-right); | |
200 | int carry = 0; | |
201 | for (size_t i = 0; i < std::max(left._digits.size(), right._digits.size()) || carry != 0; ++i) { | |
202 | if (i == left._digits.size()) left._digits.push_back(0); | |
203 | left._digits[i] += carry + (i < right._digits.size() ? right._digits[i] : 0); | |
204 | carry = left._digits[i] >= big_integer::BASE; | |
205 | if (carry != 0) left._digits[i] -= big_integer::BASE; | |
206 | } | |
207 | ||
208 | return left; | |
209 | } | |
210 | ||
211 | // прибавляет к текущему числу новое | |
212 | big_integer& big_integer::operator +=(const big_integer& value) { | |
213 | return *this = (*this + value); | |
214 | } | |
215 | ||
216 | // префиксный инкремент | |
217 | const big_integer big_integer::operator++() { | |
218 | return (*this += 1); | |
219 | } | |
220 | ||
221 | // преобразует число к строке | |
222 | big_integer::operator std::string() const { | |
223 | std::stringstream ss; | |
224 | ss << *this; | |
225 | return ss.str(); | |
226 | } | |
227 | ||
228 | // преобразует signed char к big_integer | |
229 | big_integer::big_integer(signed char c) { | |
230 | if (c < 0) this->_is_negative = true; | |
231 | else this->_is_negative = false; | |
232 | this->_digits.push_back(std::abs(c)); | |
233 | } | |
234 | ||
235 | // преобразует unsigned char к big_integer | |
236 | big_integer::big_integer(unsigned char c) { | |
237 | this->_is_negative = false; | |
238 | this->_digits.push_back(c); | |
239 | } | |
240 | ||
241 | // преобразует signed short к big_integer | |
242 | big_integer::big_integer(signed short s) { | |
243 | if (s < 0) this->_is_negative = true; | |
244 | else this->_is_negative = false; | |
245 | this->_digits.push_back(std::abs(s)); | |
246 | } | |
247 | ||
248 | // преобразует unsigned short к big_integer | |
249 | big_integer::big_integer(unsigned short s) { | |
250 | this->_is_negative = false; | |
251 | this->_digits.push_back(s); | |
252 | } | |
253 | ||
254 | // преобразует signed int к big_integer | |
255 | big_integer::big_integer(signed int i) { | |
256 | if (i < 0) this->_is_negative = true; | |
257 | else this->_is_negative = false; | |
258 | this->_digits.push_back(std::abs(i) % big_integer::BASE); | |
259 | i /= big_integer::BASE; | |
260 | if (i != 0) this->_digits.push_back(std::abs(i)); | |
261 | } | |
262 | ||
263 | // преобразует unsigned int к big_integer | |
264 | big_integer::big_integer(unsigned int i) { | |
265 | this->_digits.push_back(i % big_integer::BASE); | |
266 | i /= big_integer::BASE; | |
267 | if (i != 0) this->_digits.push_back(i); | |
268 | } | |
269 | ||
270 | // преобразует signed long к big_integer | |
271 | big_integer::big_integer(signed long l) { | |
272 | if (l < 0) this->_is_negative = true; | |
273 | else this->_is_negative = false; | |
274 | this->_digits.push_back(std::abs(l) % big_integer::BASE); | |
275 | l /= big_integer::BASE; | |
276 | if (l != 0) this->_digits.push_back(std::abs(l)); | |
277 | } | |
278 | ||
279 | // преобразует unsigned long к big_integer | |
280 | big_integer::big_integer(unsigned long l) { | |
281 | this->_digits.push_back(l % big_integer::BASE); | |
282 | l /= big_integer::BASE; | |
283 | if (l != 0) this->_digits.push_back(l); | |
284 | } | |
285 | ||
286 | // преобразует signed long long к big_integer | |
287 | big_integer::big_integer(signed long long l) { | |
288 | if (l < 0) { this->_is_negative = true; l = -l; } | |
289 | else this->_is_negative = false; | |
290 | do { | |
291 | this->_digits.push_back(l % big_integer::BASE); | |
292 | l /= big_integer::BASE; | |
293 | } while (l != 0); | |
294 | } | |
295 | ||
296 | // преобразует unsigned long long к big_integer | |
297 | big_integer::big_integer(unsigned long long l) { | |
298 | this->_is_negative = false; | |
299 | do { | |
300 | this->_digits.push_back(l % big_integer::BASE); | |
301 | l /= big_integer::BASE; | |
302 | } while (l != 0); | |
303 | } | |
304 | ||
305 | // постфиксный инкремент | |
306 | const big_integer big_integer::operator ++(int) { | |
307 | - | big_integer bi(*this); |
307 | + | |
308 | return *this - 1; | |
309 | - | return bi; |
309 | + | |
310 | ||
311 | // префиксный декремент | |
312 | const big_integer big_integer::operator --() { | |
313 | return *this -= 1; | |
314 | } | |
315 | ||
316 | // постфиксный декремент | |
317 | const big_integer big_integer::operator --(int) { | |
318 | *this -= 1; | |
319 | - | big_integer bi(*this); |
319 | + | return *this + 1; |
320 | } | |
321 | - | return bi; |
321 | + | |
322 | // вычитает два числа | |
323 | const big_integer operator -(big_integer left, const big_integer& right) { | |
324 | if (right._is_negative) return left + (-right); | |
325 | else if (left._is_negative) return -(-left + right); | |
326 | else if (left < right) return -(right - left); | |
327 | int carry = 0; | |
328 | for (size_t i = 0; i < right._digits.size() || carry != 0; ++i) { | |
329 | left._digits[i] -= carry + (i < right._digits.size() ? right._digits[i] : 0); | |
330 | carry = left._digits[i] < 0; | |
331 | if (carry != 0) left._digits[i] += big_integer::BASE; | |
332 | } | |
333 | ||
334 | left._remove_leading_zeros(); | |
335 | return left; | |
336 | } | |
337 | ||
338 | // вычитает из текущего числа новое | |
339 | big_integer& big_integer::operator -=(const big_integer& value) { | |
340 | return *this = (*this - value); | |
341 | } | |
342 | ||
343 | // перемножает два числа | |
344 | const big_integer operator *(const big_integer& left, const big_integer& right) { | |
345 | big_integer result; | |
346 | result._digits.resize(left._digits.size() + right._digits.size()); | |
347 | for (size_t i = 0; i < left._digits.size(); ++i) { | |
348 | int carry = 0; | |
349 | for (size_t j = 0; j < right._digits.size() || carry != 0; ++j) { | |
350 | long long cur = result._digits[i + j] + | |
351 | left._digits[i] * 1LL * (j < right._digits.size() ? right._digits[j] : 0) + carry; | |
352 | result._digits[i + j] = static_cast<int>(cur % big_integer::BASE); | |
353 | carry = static_cast<int>(cur / big_integer::BASE); | |
354 | } | |
355 | } | |
356 | ||
357 | result._is_negative = left._is_negative != right._is_negative; | |
358 | result._remove_leading_zeros(); | |
359 | return result; | |
360 | } | |
361 | ||
362 | // домножает текущее число на указанное | |
363 | big_integer& big_integer::operator *=(const big_integer& value) { | |
364 | return *this = (*this * value); | |
365 | } | |
366 | ||
367 | // сдвигает все разряды на 1 вправо (домножает на BASE) | |
368 | void big_integer::_shift_right() { | |
369 | if (this->_digits.size() == 0) { | |
370 | this->_digits.push_back(0); | |
371 | return; | |
372 | } | |
373 | this->_digits.push_back(this->_digits[this->_digits.size() - 1]); | |
374 | for (size_t i = this->_digits.size() - 2; i > 0; --i) this->_digits[i] = this->_digits[i - 1]; | |
375 | this->_digits[0] = 0; | |
376 | } | |
377 | ||
378 | // делит два числа | |
379 | const big_integer operator /(const big_integer& left, const big_integer& right) { | |
380 | if (right == 0) throw big_integer::divide_by_zero(); | |
381 | big_integer b = right; | |
382 | b._is_negative = false; | |
383 | big_integer result, current; | |
384 | result._digits.resize(left._digits.size()); | |
385 | for (long long i = static_cast<long long>(left._digits.size()) - 1; i >= 0; --i) { | |
386 | current._shift_right(); | |
387 | current._digits[0] = left._digits[i]; | |
388 | current._remove_leading_zeros(); | |
389 | int x = 0, l = 0, r = big_integer::BASE; | |
390 | while (l <= r) { | |
391 | int m = (l + r) / 2; | |
392 | big_integer t = b * m; | |
393 | if (t <= current) { | |
394 | x = m; | |
395 | l = m + 1; | |
396 | } | |
397 | else r = m - 1; | |
398 | } | |
399 | ||
400 | result._digits[i] = x; | |
401 | current = current - b * x; | |
402 | } | |
403 | ||
404 | result._is_negative = left._is_negative != right._is_negative; | |
405 | result._remove_leading_zeros(); | |
406 | return result; | |
407 | } | |
408 | ||
409 | // делит текущее число на указанное | |
410 | big_integer& big_integer::operator /=(const big_integer& value) { | |
411 | return *this = (*this / value); | |
412 | } | |
413 | ||
414 | // возвращает остаток от деления двух чисел | |
415 | const big_integer operator %(const big_integer& left, const big_integer& right) { | |
416 | big_integer result = left - (left / right) * right; | |
417 | if (result._is_negative) result += right; | |
418 | return result; | |
419 | } | |
420 | ||
421 | // присваивает текущему числу остаток от деления на другое число | |
422 | big_integer& big_integer::operator %=(const big_integer& value) { | |
423 | return *this = (*this % value); | |
424 | } | |
425 | ||
426 | // проверяет, является ли текущее число нечетным | |
427 | bool big_integer::odd() const { | |
428 | if (this->_digits.size() == 0) return false; | |
429 | return this->_digits[0] & 1; | |
430 | } | |
431 | ||
432 | // проверяет, является ли текущее число четным | |
433 | bool big_integer::even() const { | |
434 | return !this->odd(); | |
435 | } | |
436 | ||
437 | // возводит текущее число в указанную степень | |
438 | const big_integer big_integer::pow(big_integer n) const { | |
439 | big_integer a(*this), result(1); | |
440 | while (n != 0) { | |
441 | if (n.odd()) result *= a; | |
442 | a *= a; | |
443 | n /= 2; | |
444 | } | |
445 | ||
446 | return result; | |
447 | } |