Numere Mari

// indentare cu 2 spatii pentru ca sursa cu 3 spatii trece de 10KB =[
class big_int
{
private:
  int sign; // -1 daca numarul este negativ, +1 daca este pozitiv
  string digits; // cifrele numarului, stocate in ordine inversa

public:
  // initializare implicita cu 0
  big_int()
  {
    digits = "0";
    sign = 1;
  }

  // initializare prin intermediul unui sir de caractere
  big_int(string s)
  {
    int i;
    if (s.front() == '-')
      sign = -1,  i = 1;
    else if (s.front() == '+')
      sign = 1,  i = 1;
    else
      sign = 1,  i = 0;

    for (int j = s.size() - 1; j >= i; --j)
      digits.push_back(s[j]);
  }

  // initializare prin intermediul unui caracter
  big_int(char c)
  {
    sign = 1;
    digits.push_back(c);
  }

  // initializare prin intermediul unui numar intre -2^31 si 2^31 - 1
  big_int(int n)
  {
    if (n < 0)
      sign = -1;
    else
      sign = 1;

    n = std::abs(n);
    do {
      digits.push_back(n%10 + '0');
      n /= 10;
    } while (n);
  }

  // conversie la sir de caractere
  operator string() const
  {
    string ans;

    if (sign == -1)
    {
      ans.resize(1 + digits.size());
      ans.front() = '-';
      reverse_copy(digits.begin(), digits.end(), ans.begin() + 1);
      return ans;
    }
    else
    {
      ans.resize(digits.size());
      reverse_copy(digits.begin(), digits.end(), ans.begin());
      return ans;
    }
  }

  // comparator ==
  friend bool operator == (const big_int& a, const big_int& b)
  {
    return (a.sign == b.sign && a.digits == b.digits);
  }

  // comparator <
  friend bool operator < (const big_int& a, const big_int& b)
  {
    if (a.sign == -1 && b.sign == 1)
      return true;

    if (a.sign == 1 && b.sign == -1)
      return false;

    if (a.sign == -1 && b.sign == -1)
      return (b.abs() < a.abs());

    if (a.sign == 1 && b.sign == 1)
    {
      if (a.digits.size() < b.digits.size())
        return true;

      if (a.digits.size() > b.digits.size())
        return false;

      for (int i = a.digits.size() - 1; i >= 0; --i)
        if (a.digits[i] < b.digits[i])
          return true;
        else if (a.digits[i] > b.digits[i])
          return false;

      return false;
    }
  }

  // comparator <=
  friend bool operator <= (const big_int& a, const big_int& b)
  {
    return (a < b || a == b);
  }

  // comparator >=
  friend bool operator >= (const big_int& a, const big_int& b)
  {
    return !(a < b);
  }

  // valoarea absoluta
  big_int abs() const
  {
    big_int ans = *this;
    ans.sign = 1;

    return ans;
  }

  // opusul (inversul in raport cu adunarea)
  big_int operator - () const
  {
    if (digits == "0")
      return *this;

    big_int ans = *this;
    ans.sign *= -1;
    return ans;
  }

  // suma a 2 numere
  big_int operator + (const big_int& b) const
  {
    if (sign == -1 && b.sign == -1)
      return -(this->abs() + b.abs());

    if (sign == -1 && b.sign == 1)
      return b - this->abs();

    if (sign == 1 && b.sign == -1)
      return *this - b.abs();

    if (sign == 1 && b.sign == 1)
    {
      big_int ans;
      ans.sign = 1;
      ans.digits = "";

      int cnt = 0, i;
      for (i = 0; i < std::min(digits.size(), b.digits.size()); ++i)
      {
        int sum = digits[i]-'0' + b.digits[i]-'0' + cnt;
        ans.digits.push_back(sum%10 + '0');
        cnt = sum/10;
      }

      for (; i < digits.size(); ++i)
      {
        int sum = digits[i]-'0' + cnt;
        ans.digits.push_back(sum%10 + '0');
        cnt = sum/10;
      }

      for (; i < b.digits.size(); ++i)
      {
        int sum = b.digits[i]-'0' + cnt;
        ans.digits.push_back(sum%10 + '0');
        cnt = sum/10;
      }

      for (; cnt; cnt /= 10)
        ans.digits.push_back(cnt%10 + '0');

      return ans;
    }
  }

  // diferenta a 2 numere
  big_int operator - (const big_int& b) const
  {
    if (sign == -1 && b.sign == -1)
      return b.abs() - this->abs();

    if (sign == -1 && b.sign == 1)
      return -(this->abs() + b);

    if (sign == 1 && b.sign == -1)
      return *this + b.abs();

    if (sign == 1 && b.sign == 1)
    {
      if (*this < b)
        return -(b - *this);

      big_int ans;
      ans.sign = 1;
      ans.digits = "";
      int i;
      bool cnt = 0;

      for (i = 0; i < std::min(digits.size(), b.digits.size()); ++i)
      {
        if ((digits[i]-'0') - (b.digits[i]-'0') - cnt < 0)
        {
          ans.digits.push_back((digits[i]-'0') - (b.digits[i]-'0') - cnt + 10 + '0');
          cnt = 1;
        }
        else
        {
          ans.digits.push_back((digits[i]-'0') - (b.digits[i]-'0') - cnt + '0');
          cnt = 0;
        }
      }

      for (; i < digits.size(); ++i)
      {
        if ((digits[i]-'0') - cnt < 0)
        {
          ans.digits.push_back((digits[i]-'0') - cnt + 10 + '0');
          cnt = 1;
        }
        else
        {
          ans.digits.push_back((digits[i]-'0') - cnt + '0');
          cnt = 0;
        }
      }

      while (ans.digits.size() != 1 && ans.digits.back() == '0')
        ans.digits.pop_back();

      return ans;
    }
  }

  // produsul a 2 numere
  big_int operator * (const big_int& b) const
  {
    if (*this == big_int(0) || b == big_int(0))
      return big_int(0);

    big_int ans;
    if (sign + b.sign == 0)
      ans.sign = -1;
    else
      ans.sign = 1;
    ans.digits.resize(digits.size() + b.digits.size(), '0');

    int cnt, i, j;
    for (i = 0; i < digits.size(); ++i)
    {
      cnt = 0;

      for (j = 0; j < b.digits.size(); ++j)
      {
        int sum = (ans.digits[i+j]-'0' + (digits[i]-'0') * (b.digits[j]-'0') + cnt);
        ans.digits[i+j] = sum%10 + '0';
        cnt = sum/10;
      }

      if (cnt)
        ans.digits[i+j] = (ans.digits[i+j]-'0' + cnt) + '0';
    }

    while (ans.digits.size() != 1 && ans.digits.back() == '0')
      ans.digits.pop_back();

    if (ans.digits == "0")
      return big_int(0);
    return ans;
  }

  // catul impartirii a 2 numere
  big_int operator / (const big_int& b) const
  {
    if (*this == big_int(0))
      return big_int(0);

    big_int ans, A = this->abs(), B = b.abs();

    if (A < B)
      return big_int(0);

    big_int dei, inm;
    dei.digits = "";
    ans.digits = "";
    int i;
    for (i = digits.size() - 1; ; --i)
    {
      dei.digits.insert(dei.digits.begin(), digits[i]);
      if (dei >= B)
        break;
    }

    for (i--; i >= -1; --i)
    {
      for (int j = 0; j <= 9; ++j)
      {
        inm.digits[0] = j+'0';
        if ( !(B * inm <= dei) )
        {
          inm.digits[0]--;
          break;
        }
      }

      ans.digits.push_back(inm.digits[0]);
      dei = dei - B*inm;
      if (dei.digits == "0")
        dei.digits = "";

      if (i >= 0)
        dei.digits.insert(dei.digits.begin(), digits[i]);
    }

    if (sign + b.sign == 0)
      ans.sign = -1;
    else
      ans.sign = 1;
    reverse(ans.digits.begin(), ans.digits.end());
    return ans;
  }

  // restul impartirii a 2 numere pozitive
  big_int operator % (const big_int& b) const
  {
    return *this - *this / b * b;
  }

  // citire prin intermediul stream-urilor
  friend istream& operator >> (istream& in, big_int& n)
  {
    int i;
    string nr;
    in >> nr;

    if (nr.front() == '-')
      n.sign = -1,   i = 1;
    else if (nr.front() == '+')
      n.sign = 1,   i = 1;
    else
      n.sign = 1,   i = 0;

    if (nr == "-0")
      n.sign = +1;

    n.digits.resize(nr.size() - i);
    reverse_copy(nr.begin() + i, nr.end(), n.digits.begin());

    return in;
  }

  // scriere prin intermediul stream-urilor
  friend ostream& operator << (ostream& out, const big_int& n)
  {
    if (n.sign == -1)
      out << '-';

    for (int i = n.digits.size() - 1; i >= 0; --i)
      out << n.digits[i];

    return out;
  }
};