Advertisement
Guest User

Untitled

a guest
Apr 8th, 2020
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 15.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. class BigIntegerOverflow : public std::exception {
  8.    
  9. };
  10.  
  11. class BigInteger {
  12. public:
  13.     BigInteger();
  14.     BigInteger(const long long& number);    
  15.     BigInteger(const string& str_number);  
  16.     string toString() const;                
  17.     BigInteger& operator=(const int& num);
  18.  
  19.     // Arithmetic operators
  20.     friend BigInteger operator+(const BigInteger& left, const BigInteger& right);
  21.     friend BigInteger operator-(const BigInteger& left, const BigInteger& right);
  22.     friend BigInteger operator*(const BigInteger& left, const BigInteger& right);
  23.     friend BigInteger operator/(const BigInteger& left, const BigInteger& right);
  24.     friend BigInteger operator%(const BigInteger& left, const BigInteger& right);
  25.  
  26.     // Arithmetic operators with assigment
  27.     BigInteger& operator+=(const BigInteger& other);
  28.     BigInteger& operator-=(const BigInteger& other);
  29.     BigInteger& operator*=(const BigInteger& other);
  30.     BigInteger& operator/=(const BigInteger& other);
  31.     BigInteger& operator%=(const BigInteger& other);
  32.    
  33.     // Unary operators
  34.     BigInteger& operator++();    
  35.     BigInteger operator++(int);  
  36.     BigInteger& operator--();    
  37.     BigInteger operator--(int);  
  38.     BigInteger operator-() const;
  39.      
  40.     // Comparison operators
  41.     friend bool operator< (const BigInteger& left, const BigInteger& right);
  42.     friend bool operator> (const BigInteger& left, const BigInteger& right);
  43.     friend bool operator<=(const BigInteger& left, const BigInteger& right);
  44.     friend bool operator>=(const BigInteger& left, const BigInteger& right);
  45.     friend bool operator==(const BigInteger& left, const BigInteger& right);
  46.     friend bool operator!=(const BigInteger& left, const BigInteger& right);
  47.  
  48.     explicit operator bool() const;
  49.     friend ostream& operator<<(ostream& out, const BigInteger& num);
  50.     friend istream& operator>>(istream& in, const BigInteger& str_num);
  51.  
  52. private:
  53.     static const int BASE = 10000;
  54.     static const int BASE_LENGTH = 4;
  55.     vector<unsigned int> digits;
  56.     bool sign = false;
  57.  
  58.     unsigned int DigitsSize() const;
  59.     BigInteger base_mult(const unsigned int& degree) const;
  60.     BigInteger cut_digits(const unsigned int& begin, const unsigned int& end) const;
  61.     BigInteger inner_karatsuba_mult(const BigInteger& left, const BigInteger& right) const;
  62.     unsigned int max(const unsigned int& left, const unsigned int& right) const;
  63.     unsigned int find_max_k(const BigInteger& divider, const unsigned int& cur_digit) const;
  64. };
  65.  
  66. BigInteger operator ""_bi(const char* num) {
  67.     return BigInteger(string(num));
  68. }
  69.  
  70. unsigned int BigInteger::max(const unsigned int& left, const unsigned int& right) const {
  71.     return left > right ? left : right;
  72. }
  73.  
  74. BigInteger::BigInteger() {
  75.     *this = 0;
  76. }
  77.  
  78. BigInteger::BigInteger(const long long& number) {
  79.     long long tmp_number = number;
  80.     digits = vector<unsigned int>();
  81.     if (number < 0) {
  82.         sign = true;
  83.         tmp_number *= -1;
  84.     }
  85.     while (tmp_number > 0) {
  86.         digits.push_back(tmp_number % BASE);
  87.         tmp_number /= BASE;
  88.     }
  89. }
  90.  
  91. BigInteger::BigInteger(const string& str_number) {
  92.     string number;
  93.     if (str_number[0] == '-' && str_number != "-0") {
  94.         sign = true;
  95.         number = str_number.substr(1);
  96.     }
  97.     else
  98.         number = str_number;
  99.  
  100.     unsigned int number_end = number.length();
  101.     while (number_end > BASE_LENGTH) {
  102.         unsigned int number_begin = number_end - BASE_LENGTH;
  103.             string digit = number.substr(number_begin, BASE_LENGTH);
  104.             digits.push_back(stoi(digit));
  105.             number_end -= BASE_LENGTH;
  106.     }
  107.     string digit = number.substr(0, number_end);
  108.     digits.push_back(stoi(digit));
  109. }
  110.  
  111. BigInteger& BigInteger::operator=(const int& num) {
  112.     *this = BigInteger(num);
  113.     return *this;
  114. }
  115.  
  116. ostream& operator<<(ostream& out, const BigInteger& num) {
  117.     out << num.toString();
  118.     return out;
  119. }
  120.  
  121. istream& operator>>(istream& in, BigInteger& num) {
  122.     string str;
  123.     in >> str;
  124.     num = BigInteger(str);
  125.     return in;
  126. }
  127.  
  128. BigInteger::operator bool() const {
  129.     return digits.size() ? true : false;
  130. }
  131.  
  132. string BigInteger::toString() const {
  133.     if (!digits.size())
  134.         return "0";
  135.     string result = "";
  136.     if (sign)
  137.         result += "-";
  138.    
  139.     for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
  140.         if (it == digits.rbegin())
  141.             result += to_string(*it);
  142.         else {
  143.             for (unsigned int i = 0; i < BASE_LENGTH - to_string(*it).length(); ++i)
  144.                 result += "0";
  145.             result += to_string(*it);
  146.         }
  147.     }
  148.     return result;
  149. }
  150.  
  151. BigInteger BigInteger::operator-() const {
  152.     BigInteger result = *this;
  153.     result.sign = !sign;
  154.     return result;
  155. }
  156.  
  157. BigInteger operator+(const BigInteger& left, const BigInteger& right) {
  158.     BigInteger result = left;
  159.     result += right;
  160.     return result;
  161. }
  162.  
  163. BigInteger operator-(const BigInteger& left, const BigInteger& right) {
  164.     BigInteger result = left;
  165.     result -= right;
  166.     return result;
  167. }
  168.  
  169. BigInteger& BigInteger::operator+=(const BigInteger& other) {
  170.     if (sign && !other.sign) {
  171.         sign = !sign;
  172.         *this -= other;
  173.         sign = !sign;
  174.         return *this;
  175.     }
  176.     else if (!sign && other.sign) {
  177.         *this -= -other;
  178.         return *this;
  179.     }
  180.    
  181.     BigInteger result;
  182.     long long addition = 0;
  183.     unsigned int max_size = digits.size() > other.digits.size() ? digits.size() : other.digits.size();
  184.     unsigned int first, second;
  185.     unsigned int cur_digit;
  186.    
  187.     for (unsigned int i = 0; i < max_size; ++i) {
  188.         first = i < digits.size() ? digits[i] : 0;
  189.         second = i < other.digits.size() ? other.digits[i] : 0;
  190.         cur_digit = (first + second + addition) % BASE;
  191.         if (i < digits.size())
  192.             digits[i] = cur_digit;
  193.         else
  194.             digits.push_back(cur_digit);
  195.         addition = (first + second + addition) / BASE;
  196.     }
  197.    
  198.     if (addition)
  199.         digits.push_back(addition);
  200.     return *this;
  201. }
  202.  
  203. BigInteger& BigInteger::operator-=(const BigInteger& other) {
  204.     if (other == 0)
  205.         return *this;
  206.     if (sign && !other.sign) {
  207.         sign = !sign;
  208.         *this += other;
  209.         sign = !sign;
  210.         return *this;
  211.     }
  212.     if (!sign && other.sign) {
  213.         *this += -other;
  214.         return *this;
  215.     }
  216.     if (sign && other.sign && *this > other) {
  217.         BigInteger result = -other;
  218.         result -= -*this;
  219.         *this = result;
  220.         return *this;
  221.     }
  222.     if (!sign && !other.sign && *this < other) {
  223.         BigInteger result = other;
  224.         result -= *this;
  225.         *this = result;
  226.         sign = !sign;
  227.         return *this;
  228.     }
  229.    
  230.     BigInteger result;
  231.     long long loan = 0;
  232.     unsigned int max_size = digits.size();
  233.     unsigned int first, second;
  234.     unsigned int cur_digit;
  235.  
  236.     for (unsigned int i = 0; i < max_size; ++i) {
  237.         first = i < digits.size() ? digits[i] : 0;
  238.         second = i < other.digits.size() ? other.digits[i] : 0;
  239.         cur_digit = (2 * BASE + first - second - loan) % BASE;
  240.         if (i < digits.size())
  241.             digits[i] = cur_digit;
  242.         else
  243.             digits.push_back(cur_digit);
  244.         loan = 2 - (2 * BASE + first - second - loan) / BASE;
  245.     }
  246.    
  247.     while (digits.size() > 0 && digits[digits.size() - 1] == 0)
  248.         digits.pop_back();
  249.     if (!digits.size())
  250.         sign = false;
  251.     return *this;
  252. }
  253.  
  254. BigInteger BigInteger::cut_digits(const unsigned int& begin, const unsigned int& end) const {
  255.     BigInteger result;
  256.     for (unsigned int i = begin; i < end; ++i)
  257.         result.digits.push_back(digits[i]);
  258.     return result;
  259. }
  260.  
  261. BigInteger BigInteger::base_mult(const unsigned int& degree) const {
  262.     if (*this == 0)
  263.         return 0;
  264.     BigInteger new_num = BigInteger();
  265.     for (unsigned int i = 0; i < degree; ++i)
  266.         new_num.digits.push_back(0);
  267.     for (unsigned int digit : digits)
  268.         new_num.digits.push_back(digit);
  269.     return new_num;
  270. }
  271.  
  272. BigInteger BigInteger::inner_karatsuba_mult(const BigInteger& left, const BigInteger& right) const {
  273.     if (left == 0 || right == 0 || left == -0 || right == -0)
  274.         return 0;
  275.     unsigned int max_len = left.digits.size() > right.digits.size() ? left.digits.size() : right.digits.size();
  276.     if (max_len == 1)
  277.         return BigInteger(left.digits[0] * right.digits[0]);
  278.    
  279.     BigInteger _left = left;
  280.     BigInteger _right = right;
  281.    
  282.     while (_left.digits.size() < _right.digits.size())
  283.         _left.digits.push_back(0);
  284.     while (_left.digits.size() > _right.digits.size())
  285.         _right.digits.push_back(0);
  286.  
  287.     BigInteger left_l, left_r, right_l, right_r;
  288.     left_l = _left.cut_digits(max_len / 2, max_len);
  289.     left_r = _left.cut_digits(0, max_len / 2);
  290.     right_l = _right.cut_digits(max_len / 2, max_len);
  291.     right_r = _right.cut_digits(0, max_len / 2);
  292.  
  293.     BigInteger res1 = inner_karatsuba_mult(left_l, right_l);
  294.     BigInteger res2 = inner_karatsuba_mult(left_r, right_r);
  295.     BigInteger res3 = (inner_karatsuba_mult(left_l + left_r, right_l + right_r) - res2 - res1);
  296.  
  297.     res1 = res1.base_mult(max_len / 2 * 2);
  298.     res3 = res3.base_mult(max_len / 2);
  299.  
  300.     return res1 + res3 + res2;
  301. }
  302.  
  303. BigInteger& BigInteger::operator*=(const BigInteger& other) {       // X * Y = (A * C * BASE^n) + ((A + B) * (C + D) - A * C - B * D) * BASE^(n / 2) + B * D
  304.     bool tmp_sign = sign != other.sign;
  305.     *this = inner_karatsuba_mult(*this, other);
  306.     sign = tmp_sign;
  307.     return *this;
  308. }
  309.  
  310. unsigned int BigInteger::find_max_k(const BigInteger& divider, const unsigned int& cur_digit) const {
  311.     unsigned int left = 0;
  312.     unsigned int right = BASE + 1;
  313.     unsigned int mid;
  314.     BigInteger mid_value;
  315.     BigInteger tmp_divider = divider.base_mult(cur_digit - divider.digits.size());
  316.     while (right - left > 1) {
  317.         mid = (right + left) / 2;
  318.         mid_value = mid * tmp_divider;
  319.        
  320.         if (*this >= mid_value)
  321.             left = mid;
  322.         else
  323.             right = mid;
  324.     }
  325.     return left;
  326. }
  327.  
  328. BigInteger& BigInteger::operator/=(const BigInteger& other) {
  329.     if (other == 0)
  330.         cerr << "Division by zero" << std::endl;
  331.     if (other == 1) {
  332.         return *this;
  333.     }
  334.     BigInteger result;
  335.     bool res_sign = sign != other.sign;
  336.  
  337.     BigInteger divident = *this;
  338.     divident.sign = false;
  339.  
  340.     BigInteger divisor = other;
  341.     divisor.sign = false;
  342.  
  343.     BigInteger base_shift;
  344.  
  345.     while (divident >= divisor) {
  346.         base_shift = 1;
  347.         while (divident >= divisor * BASE) {
  348.             divisor *= BASE;
  349.             base_shift *= BASE;
  350.         }
  351.  
  352.         while (divident >= divisor) {
  353.             divident -= divisor;
  354.             result += base_shift;
  355.         }
  356.  
  357.         divisor = other;
  358.         divisor.sign = false;
  359.     }
  360.     while (result.digits.size() > 0 && result.digits[result.digits.size() - 1] == 0)
  361.         result.digits.pop_back();
  362.     if (!digits.size())
  363.         result.sign = false;
  364.     result.sign = res_sign;
  365.     *this = result;
  366.     return *this;
  367. }
  368.  
  369. BigInteger& BigInteger::operator%=(const BigInteger& other) {
  370.     BigInteger divider = other;
  371.     bool tmp_sign = sign;
  372.     sign = false;
  373.     divider.sign = false;
  374.     *this -= (*this / divider) * divider;
  375.     sign = tmp_sign;
  376.     return *this;
  377. }
  378.  
  379. BigInteger operator*(const BigInteger& left, const BigInteger& right) {
  380.     BigInteger res = left;
  381.     res *= right;
  382.     return res;
  383. }
  384.  
  385. BigInteger operator/(const BigInteger& left, const BigInteger& right) {
  386.     BigInteger result = left;
  387.     result /= right;
  388.     return result;
  389. }
  390.  
  391. BigInteger operator%(const BigInteger& left, const BigInteger& right) {
  392.     BigInteger result = left;
  393.     result %= right;
  394.     return result;
  395. }
  396.  
  397. BigInteger& BigInteger::operator++() {
  398.     if (*this == -1) {
  399.         *this = 0;
  400.         return *this;
  401.     }
  402.     if (*this == 0) {
  403.         *this = 1;
  404.         return *this;
  405.     }
  406.     if (sign) {
  407.         sign = !sign;
  408.         --*this;
  409.         sign = !sign;
  410.         return *this;
  411.     }
  412.     bool need_addition = true;
  413.     unsigned int cur_digit = 0;    
  414.     while (need_addition) {
  415.         if (digits.size() == cur_digit)
  416.             digits.push_back(0);
  417.         ++digits[cur_digit];
  418.         if (digits[cur_digit] < BASE)
  419.             need_addition = false;
  420.         else {
  421.             digits[cur_digit] = 0;
  422.         }
  423.         ++cur_digit;
  424.     }
  425.     return *this;
  426. }
  427.  
  428. BigInteger BigInteger::operator++(int) {
  429.     BigInteger cp = *this;
  430.     ++*this;
  431.     return cp;
  432. }
  433.  
  434. BigInteger& BigInteger::operator--() {
  435.     if (*this == 1) {
  436.         *this = 0;
  437.         return *this;
  438.     }
  439.     if (*this == 0) {
  440.         *this = -1;
  441.         return *this;
  442.     }
  443.     if (sign) {
  444.         sign = !sign;
  445.         ++*this;
  446.         sign = !sign;
  447.         return *this;
  448.     }
  449.     bool need_loan = true;
  450.     unsigned int cur_digit = 0;
  451.     while (need_loan) {
  452.         if (digits[cur_digit] > 0) {
  453.             need_loan = false;
  454.             --digits[cur_digit];
  455.         }
  456.         else
  457.             digits[cur_digit] = BASE - 1;
  458.         ++cur_digit;
  459.     }
  460.     if (digits[digits.size() - 1] == 0)
  461.         digits.pop_back();
  462.     return *this;
  463. }
  464.  
  465. BigInteger BigInteger::operator--(int) {
  466.     BigInteger cp = *this;
  467.     --*this;
  468.     return cp;
  469. }
  470.  
  471. bool operator<=(const BigInteger& left, const BigInteger& right) {
  472.     if (left.digits.size() == 0 && (!right.sign || right.digits.size() == 0))
  473.         return true;
  474.     unsigned int max_size = left.digits.size() > right.digits.size() ? left.digits.size() : right.digits.size();
  475.     if (left.sign && !right.sign)
  476.         return true;
  477.     if (left.sign && right.sign)
  478.         return -left >= -right;
  479.     if (right.sign)
  480.         return false;
  481.    
  482.     unsigned int first, second;
  483.     for (unsigned int i = max_size; i > 0; --i) {
  484.         first = i - 1 < left.digits.size() ? left.digits[i - 1] : 0;
  485.         second = i - 1 < right.digits.size() ? right.digits[i - 1] : 0;
  486.         if (first == second)
  487.             continue;
  488.         else
  489.             return first <= second;
  490.     }
  491.     return true;
  492. }
  493.  
  494. bool operator>=(const BigInteger& left, const BigInteger& right) {
  495.     return right <= left;
  496. }
  497.  
  498. bool operator==(const BigInteger& left, const BigInteger& right) {
  499.     return left <= right && right <= left;
  500. }
  501.  
  502. bool operator!=(const BigInteger& left, const BigInteger& right) {
  503.     return !(left == right);
  504. }
  505.  
  506. bool operator< (const BigInteger& left, const BigInteger& right) {
  507.     return left <= right && left != right;
  508. }
  509.  
  510. bool operator> (const BigInteger& left, const BigInteger& right) {
  511.     return right < left;
  512. }
  513.  
  514.  
  515.  
  516.  
  517.  
  518.  
  519. int main() {
  520.     std::ios_base::sync_with_stdio(false);
  521.     std::cin.tie(nullptr);
  522.     BigInteger a, b;
  523.     std::cin >> a >> b;
  524.     if (a>=b){
  525.         std::cout << (a / b) << '\n';
  526.         std::cout << (a % b) << '\n';
  527.     }
  528.     else{
  529.         std::cout << (b / a) << '\n';
  530.         std::cout << (b % a) << '\n';
  531.     }
  532.  
  533.  
  534.  
  535. return 0;
  536. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement