Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- using namespace std;
- class BigIntegerOverflow : public std::exception {
- };
- class BigInteger {
- public:
- BigInteger();
- BigInteger(const long long& number);
- BigInteger(const string& str_number);
- string toString() const;
- BigInteger& operator=(const int& num);
- // Arithmetic operators
- friend BigInteger operator+(const BigInteger& left, const BigInteger& right);
- friend BigInteger operator-(const BigInteger& left, const BigInteger& right);
- friend BigInteger operator*(const BigInteger& left, const BigInteger& right);
- friend BigInteger operator/(const BigInteger& left, const BigInteger& right);
- friend BigInteger operator%(const BigInteger& left, const BigInteger& right);
- // Arithmetic operators with assigment
- BigInteger& operator+=(const BigInteger& other);
- BigInteger& operator-=(const BigInteger& other);
- BigInteger& operator*=(const BigInteger& other);
- BigInteger& operator/=(const BigInteger& other);
- BigInteger& operator%=(const BigInteger& other);
- // Unary operators
- BigInteger& operator++();
- BigInteger operator++(int);
- BigInteger& operator--();
- BigInteger operator--(int);
- BigInteger operator-() const;
- // Comparison operators
- friend bool operator< (const BigInteger& left, const BigInteger& right);
- friend bool operator> (const BigInteger& left, const BigInteger& right);
- friend bool operator<=(const BigInteger& left, const BigInteger& right);
- friend bool operator>=(const BigInteger& left, const BigInteger& right);
- friend bool operator==(const BigInteger& left, const BigInteger& right);
- friend bool operator!=(const BigInteger& left, const BigInteger& right);
- explicit operator bool() const;
- friend ostream& operator<<(ostream& out, const BigInteger& num);
- friend istream& operator>>(istream& in, const BigInteger& str_num);
- private:
- static const int BASE = 10000;
- static const int BASE_LENGTH = 4;
- vector<unsigned int> digits;
- bool sign = false;
- unsigned int DigitsSize() const;
- BigInteger base_mult(const unsigned int& degree) const;
- BigInteger cut_digits(const unsigned int& begin, const unsigned int& end) const;
- BigInteger inner_karatsuba_mult(const BigInteger& left, const BigInteger& right) const;
- unsigned int max(const unsigned int& left, const unsigned int& right) const;
- unsigned int find_max_k(const BigInteger& divider, const unsigned int& cur_digit) const;
- };
- BigInteger operator ""_bi(const char* num) {
- return BigInteger(string(num));
- }
- unsigned int BigInteger::max(const unsigned int& left, const unsigned int& right) const {
- return left > right ? left : right;
- }
- BigInteger::BigInteger() {
- *this = 0;
- }
- BigInteger::BigInteger(const long long& number) {
- long long tmp_number = number;
- digits = vector<unsigned int>();
- if (number < 0) {
- sign = true;
- tmp_number *= -1;
- }
- while (tmp_number > 0) {
- digits.push_back(tmp_number % BASE);
- tmp_number /= BASE;
- }
- }
- BigInteger::BigInteger(const string& str_number) {
- string number;
- if (str_number[0] == '-' && str_number != "-0") {
- sign = true;
- number = str_number.substr(1);
- }
- else
- number = str_number;
- unsigned int number_end = number.length();
- while (number_end > BASE_LENGTH) {
- unsigned int number_begin = number_end - BASE_LENGTH;
- string digit = number.substr(number_begin, BASE_LENGTH);
- digits.push_back(stoi(digit));
- number_end -= BASE_LENGTH;
- }
- string digit = number.substr(0, number_end);
- digits.push_back(stoi(digit));
- }
- BigInteger& BigInteger::operator=(const int& num) {
- *this = BigInteger(num);
- return *this;
- }
- ostream& operator<<(ostream& out, const BigInteger& num) {
- out << num.toString();
- return out;
- }
- istream& operator>>(istream& in, BigInteger& num) {
- string str;
- in >> str;
- num = BigInteger(str);
- return in;
- }
- BigInteger::operator bool() const {
- return digits.size() ? true : false;
- }
- string BigInteger::toString() const {
- if (!digits.size())
- return "0";
- string result = "";
- if (sign)
- result += "-";
- for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
- if (it == digits.rbegin())
- result += to_string(*it);
- else {
- for (unsigned int i = 0; i < BASE_LENGTH - to_string(*it).length(); ++i)
- result += "0";
- result += to_string(*it);
- }
- }
- return result;
- }
- BigInteger BigInteger::operator-() const {
- BigInteger result = *this;
- result.sign = !sign;
- return result;
- }
- BigInteger operator+(const BigInteger& left, const BigInteger& right) {
- BigInteger result = left;
- result += right;
- return result;
- }
- BigInteger operator-(const BigInteger& left, const BigInteger& right) {
- BigInteger result = left;
- result -= right;
- return result;
- }
- BigInteger& BigInteger::operator+=(const BigInteger& other) {
- if (sign && !other.sign) {
- sign = !sign;
- *this -= other;
- sign = !sign;
- return *this;
- }
- else if (!sign && other.sign) {
- *this -= -other;
- return *this;
- }
- BigInteger result;
- long long addition = 0;
- unsigned int max_size = digits.size() > other.digits.size() ? digits.size() : other.digits.size();
- unsigned int first, second;
- unsigned int cur_digit;
- for (unsigned int i = 0; i < max_size; ++i) {
- first = i < digits.size() ? digits[i] : 0;
- second = i < other.digits.size() ? other.digits[i] : 0;
- cur_digit = (first + second + addition) % BASE;
- if (i < digits.size())
- digits[i] = cur_digit;
- else
- digits.push_back(cur_digit);
- addition = (first + second + addition) / BASE;
- }
- if (addition)
- digits.push_back(addition);
- return *this;
- }
- BigInteger& BigInteger::operator-=(const BigInteger& other) {
- if (other == 0)
- return *this;
- if (sign && !other.sign) {
- sign = !sign;
- *this += other;
- sign = !sign;
- return *this;
- }
- if (!sign && other.sign) {
- *this += -other;
- return *this;
- }
- if (sign && other.sign && *this > other) {
- BigInteger result = -other;
- result -= -*this;
- *this = result;
- return *this;
- }
- if (!sign && !other.sign && *this < other) {
- BigInteger result = other;
- result -= *this;
- *this = result;
- sign = !sign;
- return *this;
- }
- BigInteger result;
- long long loan = 0;
- unsigned int max_size = digits.size();
- unsigned int first, second;
- unsigned int cur_digit;
- for (unsigned int i = 0; i < max_size; ++i) {
- first = i < digits.size() ? digits[i] : 0;
- second = i < other.digits.size() ? other.digits[i] : 0;
- cur_digit = (2 * BASE + first - second - loan) % BASE;
- if (i < digits.size())
- digits[i] = cur_digit;
- else
- digits.push_back(cur_digit);
- loan = 2 - (2 * BASE + first - second - loan) / BASE;
- }
- while (digits.size() > 0 && digits[digits.size() - 1] == 0)
- digits.pop_back();
- if (!digits.size())
- sign = false;
- return *this;
- }
- BigInteger BigInteger::cut_digits(const unsigned int& begin, const unsigned int& end) const {
- BigInteger result;
- for (unsigned int i = begin; i < end; ++i)
- result.digits.push_back(digits[i]);
- return result;
- }
- BigInteger BigInteger::base_mult(const unsigned int& degree) const {
- if (*this == 0)
- return 0;
- BigInteger new_num = BigInteger();
- for (unsigned int i = 0; i < degree; ++i)
- new_num.digits.push_back(0);
- for (unsigned int digit : digits)
- new_num.digits.push_back(digit);
- return new_num;
- }
- BigInteger BigInteger::inner_karatsuba_mult(const BigInteger& left, const BigInteger& right) const {
- if (left == 0 || right == 0 || left == -0 || right == -0)
- return 0;
- unsigned int max_len = left.digits.size() > right.digits.size() ? left.digits.size() : right.digits.size();
- if (max_len == 1)
- return BigInteger(left.digits[0] * right.digits[0]);
- BigInteger _left = left;
- BigInteger _right = right;
- while (_left.digits.size() < _right.digits.size())
- _left.digits.push_back(0);
- while (_left.digits.size() > _right.digits.size())
- _right.digits.push_back(0);
- BigInteger left_l, left_r, right_l, right_r;
- left_l = _left.cut_digits(max_len / 2, max_len);
- left_r = _left.cut_digits(0, max_len / 2);
- right_l = _right.cut_digits(max_len / 2, max_len);
- right_r = _right.cut_digits(0, max_len / 2);
- BigInteger res1 = inner_karatsuba_mult(left_l, right_l);
- BigInteger res2 = inner_karatsuba_mult(left_r, right_r);
- BigInteger res3 = (inner_karatsuba_mult(left_l + left_r, right_l + right_r) - res2 - res1);
- res1 = res1.base_mult(max_len / 2 * 2);
- res3 = res3.base_mult(max_len / 2);
- return res1 + res3 + res2;
- }
- 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
- bool tmp_sign = sign != other.sign;
- *this = inner_karatsuba_mult(*this, other);
- sign = tmp_sign;
- return *this;
- }
- unsigned int BigInteger::find_max_k(const BigInteger& divider, const unsigned int& cur_digit) const {
- unsigned int left = 0;
- unsigned int right = BASE + 1;
- unsigned int mid;
- BigInteger mid_value;
- BigInteger tmp_divider = divider.base_mult(cur_digit - divider.digits.size());
- while (right - left > 1) {
- mid = (right + left) / 2;
- mid_value = mid * tmp_divider;
- if (*this >= mid_value)
- left = mid;
- else
- right = mid;
- }
- return left;
- }
- BigInteger& BigInteger::operator/=(const BigInteger& other) {
- if (other == 0)
- cerr << "Division by zero" << std::endl;
- if (other == 1) {
- return *this;
- }
- BigInteger result;
- bool res_sign = sign != other.sign;
- BigInteger divident = *this;
- divident.sign = false;
- BigInteger divisor = other;
- divisor.sign = false;
- BigInteger base_shift;
- while (divident >= divisor) {
- base_shift = 1;
- while (divident >= divisor * BASE) {
- divisor *= BASE;
- base_shift *= BASE;
- }
- while (divident >= divisor) {
- divident -= divisor;
- result += base_shift;
- }
- divisor = other;
- divisor.sign = false;
- }
- while (result.digits.size() > 0 && result.digits[result.digits.size() - 1] == 0)
- result.digits.pop_back();
- if (!digits.size())
- result.sign = false;
- result.sign = res_sign;
- *this = result;
- return *this;
- }
- BigInteger& BigInteger::operator%=(const BigInteger& other) {
- BigInteger divider = other;
- bool tmp_sign = sign;
- sign = false;
- divider.sign = false;
- *this -= (*this / divider) * divider;
- sign = tmp_sign;
- return *this;
- }
- BigInteger operator*(const BigInteger& left, const BigInteger& right) {
- BigInteger res = left;
- res *= right;
- return res;
- }
- BigInteger operator/(const BigInteger& left, const BigInteger& right) {
- BigInteger result = left;
- result /= right;
- return result;
- }
- BigInteger operator%(const BigInteger& left, const BigInteger& right) {
- BigInteger result = left;
- result %= right;
- return result;
- }
- BigInteger& BigInteger::operator++() {
- if (*this == -1) {
- *this = 0;
- return *this;
- }
- if (*this == 0) {
- *this = 1;
- return *this;
- }
- if (sign) {
- sign = !sign;
- --*this;
- sign = !sign;
- return *this;
- }
- bool need_addition = true;
- unsigned int cur_digit = 0;
- while (need_addition) {
- if (digits.size() == cur_digit)
- digits.push_back(0);
- ++digits[cur_digit];
- if (digits[cur_digit] < BASE)
- need_addition = false;
- else {
- digits[cur_digit] = 0;
- }
- ++cur_digit;
- }
- return *this;
- }
- BigInteger BigInteger::operator++(int) {
- BigInteger cp = *this;
- ++*this;
- return cp;
- }
- BigInteger& BigInteger::operator--() {
- if (*this == 1) {
- *this = 0;
- return *this;
- }
- if (*this == 0) {
- *this = -1;
- return *this;
- }
- if (sign) {
- sign = !sign;
- ++*this;
- sign = !sign;
- return *this;
- }
- bool need_loan = true;
- unsigned int cur_digit = 0;
- while (need_loan) {
- if (digits[cur_digit] > 0) {
- need_loan = false;
- --digits[cur_digit];
- }
- else
- digits[cur_digit] = BASE - 1;
- ++cur_digit;
- }
- if (digits[digits.size() - 1] == 0)
- digits.pop_back();
- return *this;
- }
- BigInteger BigInteger::operator--(int) {
- BigInteger cp = *this;
- --*this;
- return cp;
- }
- bool operator<=(const BigInteger& left, const BigInteger& right) {
- if (left.digits.size() == 0 && (!right.sign || right.digits.size() == 0))
- return true;
- unsigned int max_size = left.digits.size() > right.digits.size() ? left.digits.size() : right.digits.size();
- if (left.sign && !right.sign)
- return true;
- if (left.sign && right.sign)
- return -left >= -right;
- if (right.sign)
- return false;
- unsigned int first, second;
- for (unsigned int i = max_size; i > 0; --i) {
- first = i - 1 < left.digits.size() ? left.digits[i - 1] : 0;
- second = i - 1 < right.digits.size() ? right.digits[i - 1] : 0;
- if (first == second)
- continue;
- else
- return first <= second;
- }
- return true;
- }
- bool operator>=(const BigInteger& left, const BigInteger& right) {
- return right <= left;
- }
- bool operator==(const BigInteger& left, const BigInteger& right) {
- return left <= right && right <= left;
- }
- bool operator!=(const BigInteger& left, const BigInteger& right) {
- return !(left == right);
- }
- bool operator< (const BigInteger& left, const BigInteger& right) {
- return left <= right && left != right;
- }
- bool operator> (const BigInteger& left, const BigInteger& right) {
- return right < left;
- }
- int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
- BigInteger a, b;
- std::cin >> a >> b;
- if (a>=b){
- std::cout << (a / b) << '\n';
- std::cout << (a % b) << '\n';
- }
- else{
- std::cout << (b / a) << '\n';
- std::cout << (b % a) << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement