BigInteger.cpp

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;

typedef unsigned int Ui;
const Ui base = 1e+9;
const int base_digit = 9;
const int zero_code = static_cast<int>('0');
const int base_ten = 10;

struct BigInteger {
  explicit operator int() const;
  explicit operator bool() const;

  BigInteger operator-() const;
  friend BigInteger Abs(const BigInteger &bigint);

  BigInteger &operator-=(const BigInteger &bigint);
  BigInteger &operator+=(const BigInteger &bigint);
  BigInteger &operator*=(const BigInteger &bigint);
  BigInteger &operator/=(const BigInteger &bigint);
  BigInteger &operator%=(const BigInteger &bigint);

  BigInteger &operator=(const BigInteger &bigint);

  std::string ToString() const;

  friend BigInteger operator+(const BigInteger &bigint1,
                              const BigInteger &bigint2);
  friend BigInteger operator-(const BigInteger &bigint1,
                              const BigInteger &bigint2);
  friend BigInteger operator*(const BigInteger &bigint1,
                              const BigInteger &bigint2);
  friend BigInteger operator/(const BigInteger &bigint1,
                              const BigInteger &bigint2);
  friend BigInteger operator%(const BigInteger &bigint1,
                              const BigInteger &bigint2);

  friend bool operator==(const BigInteger &bigint1, const BigInteger &bigint2);
  friend bool operator!=(const BigInteger &bigint1, const BigInteger &bigint2);
  friend bool operator<(const BigInteger &bigint1, const BigInteger &bigint2);
  friend bool operator>(const BigInteger &bigint1, const BigInteger &bigint2);
  friend bool operator<=(const BigInteger &bigint1, const BigInteger &bigint2);
  friend bool operator>=(const BigInteger &bigint1, const BigInteger &bigint2);

  BigInteger &operator++();
  BigInteger operator++(int);
  BigInteger &operator--();
  BigInteger operator--(int);

  friend std::istream &operator>>(std::istream &stream, BigInteger &bigint);
  friend std::ostream &operator<<(std::ostream &stream,
                                  const BigInteger &bigint);

  BigInteger();
  BigInteger(int num);
  BigInteger(const std::string &num_record);
  ~BigInteger() { digits_rl_.clear(); }

 private:
  std::vector<Ui> digits_rl_;
  int sign_ = 1;
  int size_ = 0;

  void CalculSize();
  void FromString(const std::string &num_record);
  void Adjust();
  friend BigInteger Coppy(const BigInteger &bigint1, int start, int end);
  friend BigInteger ProductBase(const BigInteger &bigint1, int base_power);
  friend BigInteger ProductIntInt(int num1, int num2);
  friend BigInteger KaratsubaMultiply(const BigInteger &bigint1,
                                      const BigInteger &bigint2);
  friend BigInteger FindBasePower(const BigInteger &bigint1,
                                  const BigInteger &bigint2);
  friend BigInteger BinarySearch(BigInteger bigint1, BigInteger bigint2);
};

void BigInteger::CalculSize() {
  int num = digits_rl_.back();
  int answ = (digits_rl_.size() - 1) * base_digit;
  while (num > 0) {
    ++answ;
    num /= base_ten;
  }
  size_ = answ;
  if (answ == 0) {
    size_ = 1;
  }
}

void BigInteger::FromString(const std::string &num_record) {
  size_ = num_record.size();
  int start_num = 0;
  if (num_record[0] == '-') {
    if (num_record[1] != '0') {
      sign_ = -1;
    }
    --size_;
    start_num = 1;
  }
  int s_size = size_;
  digits_rl_.resize((s_size + base_digit - 1) / base_digit);
  int index = 0;
  while (s_size > 0) {
    int digit_num = start_num;
    Ui digit_on_base = 0;
    s_size <= base_digit ? 0 : digit_num = s_size - base_digit + start_num;
    for (; digit_num < s_size + start_num; ++digit_num) {
      digit_on_base *= base_ten;
      digit_on_base += static_cast<int>(num_record[digit_num]) - zero_code;
    }
    s_size -= base_digit;
    digits_rl_[index] = digit_on_base;
    ++index;
  }
}

void BigInteger::Adjust() {
  while (!digits_rl_.empty() && (digits_rl_.back() == 0)) {
    digits_rl_.pop_back();
  }
  if (digits_rl_.empty()) {
    sign_ = 1;
    digits_rl_.push_back(0);
  }
  CalculSize();
}

std::istream &operator>>(std::istream &stream, BigInteger &bigint) {
  std::string in;
  stream >> in;
  bigint = BigInteger(in);
  return stream;
}

std::ostream &operator<<(std::ostream &stream, const BigInteger &bigint) {
  stream << bigint.ToString();
  return stream;
}

BigInteger BigInteger::operator-() const {
  BigInteger bigint = *this;
  if ((digits_rl_[0] == 0) && (digits_rl_.size() == 1)) {
    return bigint;
  }
  bigint.sign_ *= -1;
  return bigint;
}

BigInteger::BigInteger() {}

BigInteger::BigInteger(int num) {
  if (num < 0) {
    sign_ = -1;
    num *= -1;
  }
  digits_rl_.push_back(num);
  CalculSize();
}

BigInteger::BigInteger(const std::string &num_record) {
  FromString(num_record);
}

BigInteger Abs(const BigInteger &bigint) {
  BigInteger abs_bigint = bigint;
  abs_bigint.sign_ = 1;
  return abs_bigint;
}

BigInteger &BigInteger::operator-=(const BigInteger &bigint) {
  *this = *this - bigint;
  return *this;
}

BigInteger &BigInteger::operator+=(const BigInteger &bigint) {
  *this = *this + bigint;
  return *this;
}

BigInteger &BigInteger::operator*=(const BigInteger &bigint) {
  *this = *this * bigint;
  return *this;
}

BigInteger &BigInteger::operator/=(const BigInteger &bigint) {
  *this = *this / bigint;
  return *this;
}

BigInteger &BigInteger::operator%=(const BigInteger &bigint) {
  *this = *this % bigint;
  return *this;
}

BigInteger &BigInteger::operator=(const BigInteger &bigint) {
  digits_rl_ = bigint.digits_rl_;
  size_ = bigint.size_;
  sign_ = bigint.sign_;
  return *this;
}

BigInteger::operator bool() const { return *this != BigInteger(0); }

BigInteger::operator int() const {
  int number = 0;
  for (int i = digits_rl_.size() - 1; i >= 0; --i) {
    number *= base;
    number += digits_rl_[i];
  }
  number *= sign_;
  return number;
}

bool operator<(const BigInteger &bigint1, const BigInteger &bigint2) {
  if (bigint1.sign_ != bigint2.sign_) {
    return bigint1.sign_ < bigint2.sign_;
  }
  if (bigint1.size_ != bigint2.size_) {
    return bigint1.size_ * bigint1.sign_ < bigint2.size_ * bigint2.sign_;
  }
  for (int i = bigint1.digits_rl_.size() - 1; i >= 0; --i) {
    if (bigint1.digits_rl_[i] != bigint2.digits_rl_[i]) {
      return bigint1.sign_ * bigint1.digits_rl_[i] <
          bigint2.sign_ * bigint2.digits_rl_[i];
    }
  }
  return false;
}

bool operator>(const BigInteger &bigint1, const BigInteger &bigint2) {
  return bigint2 < bigint1;
}

bool operator==(const BigInteger &bigint1, const BigInteger &bigint2) {
  return !(bigint1 > bigint2) && !(bigint1 < bigint2);
}

bool operator!=(const BigInteger &bigint1, const BigInteger &bigint2) {
  return !(bigint1 == bigint2);
}

bool operator<=(const BigInteger &bigint1, const BigInteger &bigint2) {
  return !(bigint1 > bigint2);
}
bool operator>=(const BigInteger &bigint1, const BigInteger &bigint2) {
  return !(bigint1 < bigint2);
}

std::string BigInteger::ToString() const {
  std::string str_record;
  bool is_first_block = true;
  if (digits_rl_[digits_rl_.size() - 1] == 0) {
    str_record += '0';
    return str_record;
  }
  if (sign_ == -1) {
    str_record += '-';
  }
  for (int i = digits_rl_.size() - 1; i >= 0; --i) {
    int digit = digits_rl_[i];
    std::vector<int> digits(base_digit);
    int index = base_digit - 1;
    while (digit > 0) {
      digits[index] = digit % base_ten;
      --index;
      digit /= base_ten;
    }
    int begin__of_digit = 0;
    is_first_block ? begin__of_digit = index + 1 : 0;
    for (; begin__of_digit < base_digit; ++begin__of_digit) {
      str_record += static_cast<char>(digits[begin__of_digit] + zero_code);
    }
    is_first_block = false;
  }
  return str_record;
}

BigInteger operator+(const BigInteger &bigint1, const BigInteger &bigint2) {
  if (bigint1.sign_ != bigint2.sign_) {
    return bigint1 - (-bigint2);
  }
  if (bigint1.size_ < bigint2.size_) {
    return bigint2 + bigint1;
  }
  BigInteger answ = bigint1;
  bool carry = false;
  for (int i = 0; i < bigint1.digits_rl_.size() || carry; ++i) {
    if (i == bigint1.digits_rl_.size()) {
      answ.digits_rl_.push_back(0);
      ++answ.size_;
    }
    int j = 0;
    i >= bigint2.digits_rl_.size() ? 0 : j = bigint2.digits_rl_[i];
    answ.digits_rl_[i] += static_cast<int>(carry) + j;
    carry = (answ.digits_rl_[i] >= base);
    if (carry) {
      answ.digits_rl_[i] -= base;
    }
  }
  answ.CalculSize();
  return answ;
}

BigInteger operator-(const BigInteger &bigint1, const BigInteger &bigint2) {
  if (bigint1.sign_ != bigint2.sign_) {
    return bigint1 + (-bigint2);
  }
  if (Abs(bigint1) < Abs(bigint2)) {
    return -(bigint2 - bigint1);
  }
  BigInteger answ = bigint1;
  bool carry = false;
  for (int i = 0; i < bigint2.digits_rl_.size() || carry; ++i) {
    int j = 0;
    i >= bigint2.digits_rl_.size() ? 0 : j = bigint2.digits_rl_[i];
    answ.digits_rl_[i] += base - static_cast<int>(carry) - j;
    carry = (answ.digits_rl_[i] < base);
    if (!carry) {
      answ.digits_rl_[i] -= base;
    }
  }
  answ.Adjust();
  return answ;
}

BigInteger &BigInteger::operator++() {
  *this += 1;
  return *this;
}

BigInteger BigInteger::operator++(int) {
  BigInteger old_number = *this;
  ++(*this);
  return old_number;
}

BigInteger &BigInteger::operator--() {
  *this -= 1;
  return *this;
}

BigInteger BigInteger::operator--(int) {
  BigInteger old_number = *this;
  *this -= 1;
  return old_number;
}

BigInteger Coppy(const BigInteger &bigint1, int start, int end) {
  BigInteger bigint2;
  bigint2.digits_rl_.resize(end - start);
  for (int i = start; i < end; ++i) {
    bigint2.digits_rl_[i - start] = bigint1.digits_rl_[i];
  }
  bigint2.CalculSize();
  return bigint2;
}

BigInteger ProductBase(const BigInteger &bigint1, int base_power) {
  BigInteger bigint2;
  bigint2.digits_rl_.resize(bigint1.digits_rl_.size() + base_power);
  for (int i = 0; i < bigint1.digits_rl_.size(); ++i) {
    bigint2.digits_rl_[i + base_power] = bigint1.digits_rl_[i];
  }
  bigint2.size_ = bigint1.size_ + base_power * base_digit;
  return bigint2;
}

BigInteger ProductIntInt(int num1, int num2) {
  BigInteger result;
  long long result_ll =
      static_cast<long long>(num1) * static_cast<long long>(num2);
  result.digits_rl_.push_back(result_ll % base);
  if (result_ll >= base) {
    result.digits_rl_.push_back(static_cast<int>(result_ll / base));
  }
  result.CalculSize();
  result.Adjust();
  return result;
}

BigInteger KaratsubaMultiply(const BigInteger &bigint1,
                             const BigInteger &bigint2) {
  BigInteger result;
  if ((bigint1.digits_rl_.size() == 1) && (bigint2.digits_rl_.size() == 1)) {
    return ProductIntInt(bigint1.digits_rl_[0], bigint2.digits_rl_[0]);
  }
  if (bigint1.digits_rl_.size() < bigint2.digits_rl_.size()) {
    return KaratsubaMultiply(bigint2, bigint1);
  }
  BigInteger long_bigint2 = bigint2;
  long_bigint2.digits_rl_.resize(bigint1.digits_rl_.size());
  long_bigint2.size_ = bigint1.size_;
  int half = bigint1.digits_rl_.size() / 2;
  BigInteger bigint1_fipart = Coppy(bigint1, 0, half);
  BigInteger bigint1_separt = Coppy(bigint1, half, bigint1.digits_rl_.size());
  BigInteger lbigint2_fipart = Coppy(long_bigint2, 0, half);
  BigInteger lbigint2_separt = Coppy(long_bigint2, half, bigint1.digits_rl_.size());
  BigInteger sum_bigint1 = bigint1_fipart + bigint1_separt;
  BigInteger sum_bigint2 = lbigint2_fipart + lbigint2_separt;
  BigInteger sum_prod = KaratsubaMultiply(sum_bigint1, sum_bigint2);
  BigInteger prod_fiparts = KaratsubaMultiply(bigint1_fipart, lbigint2_fipart);
  BigInteger prod_separts = KaratsubaMultiply(bigint1_separt, lbigint2_separt);
  BigInteger optized_prod = sum_prod - prod_fiparts - prod_separts;
  BigInteger lprod_separts = ProductBase(prod_separts, 2 * half);
  BigInteger loptized_prod = ProductBase(optized_prod, half);
  result = lprod_separts + loptized_prod + prod_fiparts;
  result.Adjust();
  result.CalculSize();
  return result;
}

BigInteger operator*(const BigInteger &bigint1, const BigInteger &bigint2) {
  if ((bigint1 == 0) || (bigint2 == 0)) {
    return 0;
  }
  BigInteger answ = KaratsubaMultiply(Abs(bigint1), Abs(bigint2));
  answ.sign_ = bigint1.sign_ * bigint2.sign_;
  return answ;
}

BigInteger FindBasePower(const BigInteger &bigint1, const BigInteger &bigint2) {
  int base_power = bigint1.digits_rl_.size() - bigint2.digits_rl_.size() - 1;
  if (base_power < 0) {
    return 1;
  }
  BigInteger bigint_base(base);
  BigInteger checker;
  if (base_power == 0) {
    checker = 1;
  } else {
    checker = ProductBase(bigint_base, base_power - 1);
  }
  if (base * checker * bigint2 > bigint1) {
    return checker;
  }
  return checker * base;
}

BigInteger BinarySearch(BigInteger bigint1, BigInteger bigint2) {
  if (Abs(bigint1) < Abs(bigint2)) {
    return BigInteger(0);
  }
  BigInteger answ(0);
  while (bigint1 >= bigint2) {
    BigInteger base_power = FindBasePower(bigint1, bigint2);
    BigInteger botton = base_power * bigint2;
    int left = 1;
    int right = base;
    while (left + 1 < right) {
      int middle = (left + right) / 2;
      if (middle * botton <= bigint1) {
        left = middle;
      } else {
        right = middle;
      }
    }
    bigint1 -= botton * left;
    answ += left * base_power;
  }
  return answ;
}

BigInteger operator/(const BigInteger &bigint1, const BigInteger &bigint2) {
  if (bigint1 == 0) {
    return 0;
  }
  BigInteger answ = BinarySearch(Abs(bigint1), Abs(bigint2));
  answ.sign_ = bigint1.sign_ * bigint2.sign_;
  return answ;
}

BigInteger operator%(const BigInteger &bigint1, const BigInteger &bigint2) {
  return bigint1 - (bigint1 / bigint2) * bigint2;
}