Al3XS0n

BigInteger ver1.0

Mar 29th, 2020
395
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.01 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. typedef std::vector<long long> BigInt;
  6.  
  7. class BigInteger {
  8. private:
  9.     BigInt _data;
  10.     bool _is_negative;
  11.  
  12.     static const int _base = 1000 * 1000 * 1000;
  13.  
  14.     void _reverse();
  15.  
  16.     friend std::pair<BigInteger, BigInteger> _div_mod(const BigInteger& left, const BigInteger& right);
  17.  
  18.     BigInt _karatsuba_Multiply(const BigInt& a, const BigInt& b);
  19.  
  20.     BigInt _convert_base(const BigInt& a, int old_digits, int new_digits);
  21.  
  22. public:
  23.  
  24.     BigInteger() : _is_negative(false) {}
  25.  
  26.     BigInteger(long long target) {
  27.         *this = target;
  28.     }
  29.  
  30.     void correct();
  31.  
  32.     std::string toString() const;
  33.  
  34.     friend std::ostream& operator<<(std::ostream& out, const BigInteger& target);
  35.  
  36.     friend std::istream& operator>>(std::istream& in, BigInteger& target);
  37.  
  38.     BigInteger& operator=(const BigInteger& target);
  39.  
  40.     BigInteger& operator=(long long target);
  41.  
  42.     const BigInteger& operator*=(long long right);
  43.  
  44.     const BigInteger& operator/=(long long right);
  45.  
  46.     BigInteger operator-() const;
  47.  
  48.     friend const BigInteger operator%(const BigInteger& left, const BigInteger& right);
  49.  
  50.     friend const BigInteger operator*(const BigInteger& left, const BigInteger& right);
  51.  
  52.     friend const BigInteger operator*(const BigInteger& left, long long right);
  53.  
  54.     friend const BigInteger operator/(const BigInteger& left, const BigInteger& right);
  55.  
  56.     friend const BigInteger operator/(const BigInteger& left, long long right);
  57.  
  58.     friend const BigInteger operator-(const BigInteger& left, const BigInteger& right);
  59.  
  60.     friend const BigInteger operator+(const BigInteger& left, const BigInteger& right);
  61.  
  62.  
  63.     friend bool operator==(const BigInteger& left, const BigInteger& right);
  64.  
  65.     friend bool operator<(const BigInteger& left, const BigInteger& right);
  66.  
  67.     friend bool operator!=(const BigInteger& left, const BigInteger& right);
  68.  
  69.     friend bool operator<=(const BigInteger& left, const BigInteger& right);
  70.  
  71.     friend bool operator>(const BigInteger& left, const BigInteger& right);
  72.  
  73.     friend bool operator>=(const BigInteger& left, const BigInteger& right);
  74.  
  75. };
  76.  
  77. void BigInteger::_reverse() {
  78.     for (size_t i = 0; i < this->_data.size() / 2; ++i) {
  79.         std::swap(this->_data[i], this->_data[this->_data.size() - 1 - i]);
  80.     }
  81. }
  82.  
  83. void BigInteger::correct() {
  84.     while (this->_data.size() > 1 && this->_data.back() == 0) {
  85.         this->_data.pop_back();
  86.     }
  87.     if (this->_data.size() == 1 && this->_data[0] == 0) {
  88.         this->_is_negative = false;
  89.     }
  90. }
  91.  
  92. std::pair<BigInteger, BigInteger> _div_mod(const BigInteger& left, const BigInteger& right) {
  93.     int norm = left._base / (right._data.back() + 1);
  94.     BigInteger a = left * norm;
  95.     BigInteger b = right * norm;
  96.     a._is_negative = false;
  97.     b._is_negative = false;
  98.     BigInteger q, r;
  99.     q._data.resize(a._data.size());
  100.  
  101.     for (int i = a._data.size() - 1; i >= 0; i--) {
  102.         r = r * BigInteger::_base;
  103.         r = r + a._data[i];
  104.         int s1 = r._data.size() <= b._data.size() ? 0 : r._data[b._data.size()];
  105.         int s2 = r._data.size() <= b._data.size() - 1 ? 0 : r._data[b._data.size() - 1];
  106.         int d = ((long long)BigInteger::_base * s1 + s2) / b._data.back();
  107.         r = r - b * d;
  108.         while (r._is_negative) {
  109.             r = r + b;
  110.             --d;
  111.         }
  112.         q._data[i] = d;
  113.     }
  114.  
  115.     q._is_negative = left._is_negative * right._is_negative;
  116.     r._is_negative = left._is_negative;
  117.     q.correct();
  118.     r.correct();
  119.     return std::make_pair(q, r / norm);
  120. }
  121.  
  122. std::string BigInteger::toString() const {
  123.     std::string s;
  124.     if (_is_negative) {
  125.         s += '-';
  126.     }
  127.     for (int i = (int) _data.size() - 1; i >= 0; --i) {
  128.         s += std::to_string(_data[i]);
  129.     }
  130.     return s;
  131. }
  132.  
  133. std::ostream& operator<<(std::ostream& out, const BigInteger& target) {
  134.     if (target._data.empty()) {
  135.         out << 0;
  136.     } else {
  137.         out << target.toString();
  138.     }
  139.     return out;
  140. }
  141.  
  142. std::istream& operator>>(std::istream& in, BigInteger& target) {
  143.     std::string s;
  144.     in >> s;
  145.     if (s.size() == 0) {
  146.         target._is_negative = false;
  147.     } else {
  148.         if (s[0] == '-') {
  149.             s = s.substr(1);
  150.             target._is_negative = true;
  151.         } else {
  152.             target._is_negative = false;
  153.         }
  154.         for (long long i = s.size(); i > 0; i -= 9) {
  155.             if (i < 9) {
  156.                 target._data.push_back(atoi(s.substr(0, i).c_str()));
  157.             } else {
  158.                 target._data.push_back(atoi(s.substr(i - 9, 9).c_str()));
  159.             }
  160.         }
  161.         target.correct();
  162.     }
  163.  
  164.     return in;
  165. }
  166.  
  167. BigInteger BigInteger::operator-() const {
  168.     BigInteger copy(*this);
  169.     copy._is_negative = !copy._is_negative;
  170.     return copy;
  171. }
  172.  
  173. BigInteger& BigInteger::operator=(const BigInteger& target) {
  174.     _data = target._data;
  175.     _is_negative = target._is_negative;
  176.     return *this;
  177. }
  178.  
  179. BigInteger& BigInteger::operator=(long long target) {
  180.     _is_negative = false;
  181.     if (target < 0) {
  182.         _is_negative = true;
  183.         target = -target;
  184.     }
  185.     for (; target > 0; target = target / _base) {
  186.         _data.push_back(target % _base);
  187.     }
  188.     return *this;
  189. }
  190.  
  191. const BigInteger operator+(const BigInteger& left, const BigInteger& right) {
  192.     BigInteger res = left;
  193.     if (res._is_negative) {
  194.         if (right._is_negative) {
  195.             return -(-res + (-right));
  196.         } else {
  197.             return right - (-res);
  198.         }
  199.     } else if (right._is_negative) {
  200.         return res - (-right);
  201.     }
  202.     int carry = 0;
  203.     for (size_t i = 0; i < std::max(left._data.size(), right._data.size()) || carry != 0; ++i) {
  204.         if (i == left._data.size()) {
  205.             res._data.push_back(0);
  206.         }
  207.         res._data[i] += carry + (i < right._data.size() ? right._data[i] : 0);
  208.         carry = (res._data[i] >= BigInteger::_base);
  209.         if (carry != 0) {
  210.             res._data[i] -= BigInteger::_base;
  211.         }
  212.     }
  213.     return res;
  214. }
  215.  
  216. const BigInteger operator-(const BigInteger& left, const BigInteger& right) {
  217.     if (right._is_negative) {
  218.         return left + (-right);
  219.     } else if (left._is_negative) {
  220.         return -(-left + right);
  221.     } else if (left < right) {
  222.         return -(right - left);
  223.     }
  224.     int carry = 0;
  225.     BigInteger res = left;
  226.     for (size_t i = 0; i < right._data.size() || carry != 0; ++i) {
  227.         res._data[i] -= carry + (i < right._data.size() ? right._data[i] : 0);
  228.         carry = res._data[i] < 0;
  229.         if (carry != 0) {
  230.             res._data[i] += BigInteger::_base;
  231.         }
  232.     }
  233.     res.correct();
  234.     return res;
  235. }
  236.  
  237. const BigInteger& BigInteger::operator/=(long long right) {
  238.     if (right < 0) {
  239.         _is_negative ^= 1;
  240.         right = -right;
  241.     }
  242.     for (int i = (int) _data.size() - 1, rem = 0; i >= 0; --i) {
  243.         long long cur = _data[i] + rem * (long long)_base;
  244.         _data[i] = (int) (cur / right);
  245.         rem = (int) (cur % right);
  246.     }
  247.     correct();
  248.     return *this;
  249. }
  250.  
  251. const BigInteger operator/(const BigInteger& left, long long right) {
  252.     BigInteger res = left;
  253.     res /= right;
  254.     return res;
  255. }
  256.  
  257. const BigInteger operator/(const BigInteger& left, const BigInteger& right) {
  258.     return  _div_mod(left, right).first;
  259. }
  260.  
  261. const BigInteger operator%(const BigInteger& left, const BigInteger& right) {
  262.     return _div_mod(left, right).second;
  263. }
  264.  
  265. const BigInteger& BigInteger::operator*=(long long right) {
  266.     if (right < 0) {
  267.         _is_negative ^= 1;
  268.         right = -right;
  269.     }
  270.     for (int i = 0, carry = 0; i < (int) _data.size() || carry; ++i) {
  271.         if (i == (int) _data.size()) {
  272.             _data.push_back(0);
  273.         }
  274.         long long cur = _data[i] * (long long) right + carry;
  275.         carry = (int) (cur / _base);
  276.         _data[i] = (int) (cur % _base);
  277.     }
  278.     correct();
  279.     return *this;
  280. }
  281.  
  282. const BigInteger operator*(const BigInteger& left, const long long right) {
  283.     BigInteger res = left;
  284.     res *= right;
  285.     return res;
  286. }
  287.  
  288. BigInt _karatsuba_Multiply(const BigInt& a, const BigInt& b) {
  289.     int n = a.size();
  290.     BigInt res(n + n);
  291.     if (n <= 32) {
  292.         for (int i = 0; i < n; i++) {
  293.             for (int j = 0; j < n; j++) {
  294.                 res[i + j] += a[i] * b[j];
  295.             }
  296.         }
  297.         return res;
  298.     }
  299.  
  300.     int k = n >> 1;
  301.     BigInt a1(a.begin(), a.begin() + k);
  302.     BigInt a2(a.begin() + k, a.end());
  303.     BigInt b1(b.begin(), b.begin() + k);
  304.     BigInt b2(b.begin() + k, b.end());
  305.  
  306.     BigInt a1b1 = _karatsuba_Multiply(a1, b1);
  307.     BigInt a2b2 = _karatsuba_Multiply(a2, b2);
  308.  
  309.     for (int i = 0; i < k; i++) {
  310.         a2[i] += a1[i];
  311.         b2[i] += b1[i];
  312.     }
  313.  
  314.     BigInt r = _karatsuba_Multiply(a2, b2);
  315.     for (int i = 0; i < (int) a1b1.size(); i++) {
  316.         r[i] -= a1b1[i];
  317.     }
  318.     for (int i = 0; i < (int) a2b2.size(); i++) {
  319.         r[i] -= a2b2[i];
  320.     }
  321.  
  322.     for (int i = 0; i < (int) r.size(); i++) {
  323.         res[i + k] += r[i];
  324.     }
  325.     for (int i = 0; i < (int) a1b1.size(); i++) {
  326.         res[i] += a1b1[i];
  327.     }
  328.     for (int i = 0; i < (int) a2b2.size(); i++) {
  329.         res[i + n] += a2b2[i];
  330.     }
  331.     return res;
  332. }
  333.  
  334. BigInt _convert_base(const BigInt& a, int old_digits, int new_digits) {
  335.     BigInt p(std::max(old_digits, new_digits) + 1);
  336.     p[0] = 1;
  337.     for (int i = 1; i < (int) p.size(); i++) {
  338.         p[i] = p[i - 1] * 10;
  339.     }
  340.     BigInt res;
  341.     long long cur = 0;
  342.     int cur_digits = 0;
  343.     for (int i = 0; i < (int) a.size(); i++) {
  344.         cur += a[i] * p[cur_digits];
  345.         cur_digits += old_digits;
  346.         while (cur_digits >= new_digits) {
  347.             res.push_back(int(cur % p[new_digits]));
  348.             cur /= p[new_digits];
  349.             cur_digits -= new_digits;
  350.         }
  351.     }
  352.     res.push_back((int) cur);
  353.     while (!res.empty() && !res.back()) {
  354.         res.pop_back();
  355.     }
  356.     return res;
  357. }
  358.  
  359. const BigInteger operator*(const BigInteger& left, const BigInteger& right) {
  360.     BigInt left6 = _convert_base(left._data, 9, 6);
  361.     BigInt right6 = _convert_base(right._data, 9, 6);
  362.     BigInt a(left6.begin(), left6.end());
  363.     BigInt b(right6.begin(), right6.end());
  364.  
  365.     while (a.size() < b.size()) {
  366.         a.push_back(0);
  367.     }
  368.     while (b.size() < a.size()) {
  369.         b.push_back(0);
  370.     }
  371.     while (a.size() & (a.size() - 1)) {
  372.         a.push_back(0), b.push_back(0);
  373.     }
  374.     BigInt c = _karatsuba_Multiply(a, b);
  375.     BigInteger res;
  376.     res._is_negative = left._is_negative * right._is_negative;
  377.     for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  378.         long long cur = c[i] + carry;
  379.         res._data.push_back((int) (cur % 1000000));
  380.         carry = (int) (cur / 1000000);
  381.     }
  382.     res._data = _convert_base(res._data, 6, 9);
  383.     res.correct();
  384.     return res;
  385. }
  386.  
  387. bool operator==(const BigInteger& left, const BigInteger& right) {
  388.     if (left._is_negative != right._is_negative) {
  389.         return false;
  390.     }
  391.     if (left._data.empty()) {
  392.         if (right._data.empty() || (right._data.size() == 1 && right._data[0] == 0)) {
  393.             return true;
  394.         } else {
  395.             return false;
  396.         }
  397.     }
  398.     if (right._data.empty()) {
  399.         if (left._data.size() == 1 && left._data[0] == 0) {
  400.             return true;
  401.         } else {
  402.             return false;
  403.         }
  404.     }
  405.     if (left._data.size() != right._data.size()) {
  406.         return false;
  407.     }
  408.     for (size_t i = 0; i < left._data.size(); ++i) {
  409.         if (left._data[i] != right._data[i]) {
  410.             return false;
  411.         }
  412.     }
  413.  
  414.     return true;
  415. }
  416.  
  417. bool operator<(const BigInteger& left, const BigInteger& right) {
  418.     if (left == right) return false;
  419.     if (left._is_negative) {
  420.         if (right._is_negative) {
  421.             return ((-right) < (-left));
  422.         } else {
  423.             return true;
  424.         }
  425.     } else if (right._is_negative) {
  426.         return false;
  427.     } else {
  428.         if (left._data.size() != right._data.size()) {
  429.             return left._data.size() < right._data.size();
  430.         } else {
  431.             for (long long i = left._data.size() - 1; i >= 0; --i) {
  432.                 if (left._data[i] != right._data[i]) {
  433.                     return left._data[i] < right._data[i];
  434.                 }
  435.             }
  436.             return false;
  437.         }
  438.     }
  439. }
  440.  
  441. bool operator!=(const BigInteger& left, const BigInteger& right) {
  442.     return !(left == right);
  443. }
  444.  
  445. bool operator<=(const BigInteger& left, const BigInteger& right) {
  446.     return (left < right || left == right);
  447. }
  448.  
  449. bool operator>(const BigInteger& left, const BigInteger& right) {
  450.     return !(left <= right);
  451. }
  452.  
  453. bool operator>=(const BigInteger& left, const BigInteger& right) {
  454.     return !(left < right);
  455. }
  456.  
  457. int main() {
  458.     BigInteger a, b, c;
  459.     std::cin >> a >> b;
  460.     //std::cout << a * b << ' ' << a / b << ' ' << a % b << ' ' << a + b << ' ' << a - b;
  461.     std::cout << a + b << ' ' << a - b << ' ' << a / b << ' ' << a % b << std::endl;
  462.     std::cout << a * b;
  463. }
Advertisement
Add Comment
Please, Sign In to add comment