Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- typedef std::vector<long long> BigInt;
- class BigInteger {
- private:
- BigInt _data;
- bool _is_negative;
- static const int _base = 1000 * 1000 * 1000;
- void _reverse();
- friend std::pair<BigInteger, BigInteger> _div_mod(const BigInteger& left, const BigInteger& right);
- BigInt _karatsuba_Multiply(const BigInt& a, const BigInt& b);
- BigInt _convert_base(const BigInt& a, int old_digits, int new_digits);
- public:
- BigInteger() : _is_negative(false) {}
- BigInteger(long long target) {
- *this = target;
- }
- void correct();
- std::string toString() const;
- friend std::ostream& operator<<(std::ostream& out, const BigInteger& target);
- friend std::istream& operator>>(std::istream& in, BigInteger& target);
- BigInteger& operator=(const BigInteger& target);
- BigInteger& operator=(long long target);
- const BigInteger& operator*=(long long right);
- const BigInteger& operator/=(long long right);
- BigInteger operator-() const;
- friend const BigInteger operator%(const BigInteger& left, const BigInteger& right);
- friend const BigInteger operator*(const BigInteger& left, const BigInteger& right);
- friend const BigInteger operator*(const BigInteger& left, long long right);
- friend const BigInteger operator/(const BigInteger& left, const BigInteger& right);
- friend const BigInteger operator/(const BigInteger& left, long long right);
- friend const BigInteger operator-(const BigInteger& left, const BigInteger& right);
- friend const BigInteger 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);
- friend bool operator>=(const BigInteger& left, const BigInteger& right);
- };
- void BigInteger::_reverse() {
- for (size_t i = 0; i < this->_data.size() / 2; ++i) {
- std::swap(this->_data[i], this->_data[this->_data.size() - 1 - i]);
- }
- }
- void BigInteger::correct() {
- while (this->_data.size() > 1 && this->_data.back() == 0) {
- this->_data.pop_back();
- }
- if (this->_data.size() == 1 && this->_data[0] == 0) {
- this->_is_negative = false;
- }
- }
- std::pair<BigInteger, BigInteger> _div_mod(const BigInteger& left, const BigInteger& right) {
- int norm = left._base / (right._data.back() + 1);
- BigInteger a = left * norm;
- BigInteger b = right * norm;
- a._is_negative = false;
- b._is_negative = false;
- BigInteger q, r;
- q._data.resize(a._data.size());
- for (int i = a._data.size() - 1; i >= 0; i--) {
- r = r * BigInteger::_base;
- r = r + a._data[i];
- int s1 = r._data.size() <= b._data.size() ? 0 : r._data[b._data.size()];
- int s2 = r._data.size() <= b._data.size() - 1 ? 0 : r._data[b._data.size() - 1];
- int d = ((long long)BigInteger::_base * s1 + s2) / b._data.back();
- r = r - b * d;
- while (r._is_negative) {
- r = r + b;
- --d;
- }
- q._data[i] = d;
- }
- q._is_negative = left._is_negative * right._is_negative;
- r._is_negative = left._is_negative;
- q.correct();
- r.correct();
- return std::make_pair(q, r / norm);
- }
- std::string BigInteger::toString() const {
- std::string s;
- if (_is_negative) {
- s += '-';
- }
- for (int i = (int) _data.size() - 1; i >= 0; --i) {
- s += std::to_string(_data[i]);
- }
- return s;
- }
- std::ostream& operator<<(std::ostream& out, const BigInteger& target) {
- if (target._data.empty()) {
- out << 0;
- } else {
- out << target.toString();
- }
- return out;
- }
- std::istream& operator>>(std::istream& in, BigInteger& target) {
- std::string s;
- in >> s;
- if (s.size() == 0) {
- target._is_negative = false;
- } else {
- if (s[0] == '-') {
- s = s.substr(1);
- target._is_negative = true;
- } else {
- target._is_negative = false;
- }
- for (long long i = s.size(); i > 0; i -= 9) {
- if (i < 9) {
- target._data.push_back(atoi(s.substr(0, i).c_str()));
- } else {
- target._data.push_back(atoi(s.substr(i - 9, 9).c_str()));
- }
- }
- target.correct();
- }
- return in;
- }
- BigInteger BigInteger::operator-() const {
- BigInteger copy(*this);
- copy._is_negative = !copy._is_negative;
- return copy;
- }
- BigInteger& BigInteger::operator=(const BigInteger& target) {
- _data = target._data;
- _is_negative = target._is_negative;
- return *this;
- }
- BigInteger& BigInteger::operator=(long long target) {
- _is_negative = false;
- if (target < 0) {
- _is_negative = true;
- target = -target;
- }
- for (; target > 0; target = target / _base) {
- _data.push_back(target % _base);
- }
- return *this;
- }
- const BigInteger operator+(const BigInteger& left, const BigInteger& right) {
- BigInteger res = left;
- if (res._is_negative) {
- if (right._is_negative) {
- return -(-res + (-right));
- } else {
- return right - (-res);
- }
- } else if (right._is_negative) {
- return res - (-right);
- }
- int carry = 0;
- for (size_t i = 0; i < std::max(left._data.size(), right._data.size()) || carry != 0; ++i) {
- if (i == left._data.size()) {
- res._data.push_back(0);
- }
- res._data[i] += carry + (i < right._data.size() ? right._data[i] : 0);
- carry = (res._data[i] >= BigInteger::_base);
- if (carry != 0) {
- res._data[i] -= BigInteger::_base;
- }
- }
- return res;
- }
- const BigInteger operator-(const BigInteger& left, const BigInteger& right) {
- if (right._is_negative) {
- return left + (-right);
- } else if (left._is_negative) {
- return -(-left + right);
- } else if (left < right) {
- return -(right - left);
- }
- int carry = 0;
- BigInteger res = left;
- for (size_t i = 0; i < right._data.size() || carry != 0; ++i) {
- res._data[i] -= carry + (i < right._data.size() ? right._data[i] : 0);
- carry = res._data[i] < 0;
- if (carry != 0) {
- res._data[i] += BigInteger::_base;
- }
- }
- res.correct();
- return res;
- }
- const BigInteger& BigInteger::operator/=(long long right) {
- if (right < 0) {
- _is_negative ^= 1;
- right = -right;
- }
- for (int i = (int) _data.size() - 1, rem = 0; i >= 0; --i) {
- long long cur = _data[i] + rem * (long long)_base;
- _data[i] = (int) (cur / right);
- rem = (int) (cur % right);
- }
- correct();
- return *this;
- }
- const BigInteger operator/(const BigInteger& left, long long right) {
- BigInteger res = left;
- res /= right;
- return res;
- }
- const BigInteger operator/(const BigInteger& left, const BigInteger& right) {
- return _div_mod(left, right).first;
- }
- const BigInteger operator%(const BigInteger& left, const BigInteger& right) {
- return _div_mod(left, right).second;
- }
- const BigInteger& BigInteger::operator*=(long long right) {
- if (right < 0) {
- _is_negative ^= 1;
- right = -right;
- }
- for (int i = 0, carry = 0; i < (int) _data.size() || carry; ++i) {
- if (i == (int) _data.size()) {
- _data.push_back(0);
- }
- long long cur = _data[i] * (long long) right + carry;
- carry = (int) (cur / _base);
- _data[i] = (int) (cur % _base);
- }
- correct();
- return *this;
- }
- const BigInteger operator*(const BigInteger& left, const long long right) {
- BigInteger res = left;
- res *= right;
- return res;
- }
- BigInt _karatsuba_Multiply(const BigInt& a, const BigInt& b) {
- int n = a.size();
- BigInt res(n + n);
- if (n <= 32) {
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- res[i + j] += a[i] * b[j];
- }
- }
- return res;
- }
- int k = n >> 1;
- BigInt a1(a.begin(), a.begin() + k);
- BigInt a2(a.begin() + k, a.end());
- BigInt b1(b.begin(), b.begin() + k);
- BigInt b2(b.begin() + k, b.end());
- BigInt a1b1 = _karatsuba_Multiply(a1, b1);
- BigInt a2b2 = _karatsuba_Multiply(a2, b2);
- for (int i = 0; i < k; i++) {
- a2[i] += a1[i];
- b2[i] += b1[i];
- }
- BigInt r = _karatsuba_Multiply(a2, b2);
- for (int i = 0; i < (int) a1b1.size(); i++) {
- r[i] -= a1b1[i];
- }
- for (int i = 0; i < (int) a2b2.size(); i++) {
- r[i] -= a2b2[i];
- }
- for (int i = 0; i < (int) r.size(); i++) {
- res[i + k] += r[i];
- }
- for (int i = 0; i < (int) a1b1.size(); i++) {
- res[i] += a1b1[i];
- }
- for (int i = 0; i < (int) a2b2.size(); i++) {
- res[i + n] += a2b2[i];
- }
- return res;
- }
- BigInt _convert_base(const BigInt& a, int old_digits, int new_digits) {
- BigInt p(std::max(old_digits, new_digits) + 1);
- p[0] = 1;
- for (int i = 1; i < (int) p.size(); i++) {
- p[i] = p[i - 1] * 10;
- }
- BigInt res;
- long long cur = 0;
- int cur_digits = 0;
- for (int i = 0; i < (int) a.size(); i++) {
- cur += a[i] * p[cur_digits];
- cur_digits += old_digits;
- while (cur_digits >= new_digits) {
- res.push_back(int(cur % p[new_digits]));
- cur /= p[new_digits];
- cur_digits -= new_digits;
- }
- }
- res.push_back((int) cur);
- while (!res.empty() && !res.back()) {
- res.pop_back();
- }
- return res;
- }
- const BigInteger operator*(const BigInteger& left, const BigInteger& right) {
- BigInt left6 = _convert_base(left._data, 9, 6);
- BigInt right6 = _convert_base(right._data, 9, 6);
- BigInt a(left6.begin(), left6.end());
- BigInt b(right6.begin(), right6.end());
- while (a.size() < b.size()) {
- a.push_back(0);
- }
- while (b.size() < a.size()) {
- b.push_back(0);
- }
- while (a.size() & (a.size() - 1)) {
- a.push_back(0), b.push_back(0);
- }
- BigInt c = _karatsuba_Multiply(a, b);
- BigInteger res;
- res._is_negative = left._is_negative * right._is_negative;
- for (int i = 0, carry = 0; i < (int) c.size(); i++) {
- long long cur = c[i] + carry;
- res._data.push_back((int) (cur % 1000000));
- carry = (int) (cur / 1000000);
- }
- res._data = _convert_base(res._data, 6, 9);
- res.correct();
- return res;
- }
- bool operator==(const BigInteger& left, const BigInteger& right) {
- if (left._is_negative != right._is_negative) {
- return false;
- }
- if (left._data.empty()) {
- if (right._data.empty() || (right._data.size() == 1 && right._data[0] == 0)) {
- return true;
- } else {
- return false;
- }
- }
- if (right._data.empty()) {
- if (left._data.size() == 1 && left._data[0] == 0) {
- return true;
- } else {
- return false;
- }
- }
- if (left._data.size() != right._data.size()) {
- return false;
- }
- for (size_t i = 0; i < left._data.size(); ++i) {
- if (left._data[i] != right._data[i]) {
- return false;
- }
- }
- return true;
- }
- bool operator<(const BigInteger& left, const BigInteger& right) {
- if (left == right) return false;
- if (left._is_negative) {
- if (right._is_negative) {
- return ((-right) < (-left));
- } else {
- return true;
- }
- } else if (right._is_negative) {
- return false;
- } else {
- if (left._data.size() != right._data.size()) {
- return left._data.size() < right._data.size();
- } else {
- for (long long i = left._data.size() - 1; i >= 0; --i) {
- if (left._data[i] != right._data[i]) {
- return left._data[i] < right._data[i];
- }
- }
- return false;
- }
- }
- }
- 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 !(left <= right);
- }
- bool operator>=(const BigInteger& left, const BigInteger& right) {
- return !(left < right);
- }
- int main() {
- BigInteger a, b, c;
- std::cin >> a >> b;
- //std::cout << a * b << ' ' << a / b << ' ' << a % b << ' ' << a + b << ' ' << a - b;
- std::cout << a + b << ' ' << a - b << ' ' << a / b << ' ' << a % b << std::endl;
- std::cout << a * b;
- }
Advertisement
Add Comment
Please, Sign In to add comment