Guest User

Untitled

a guest
Mar 9th, 2013
3,826
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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.     *this += 1;
  308.     return *this - 1;
  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.     return *this + 1;
  320. }
  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. }
RAW Paste Data