Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class big_int
- {
- private:
- int sign; // -1 daca numarul este negativ, +1 daca este pozitiv
- string digits; // cifrele numarului, stocate in ordine inversa
- public:
- big_int()
- {
- digits = "0";
- sign = 1;
- }
- 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]);
- }
- big_int(char c)
- {
- sign = 1;
- digits.push_back(c);
- }
- 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);
- }
- 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;
- }
- }
- friend bool operator == (const big_int& a, const big_int& b)
- {
- return (a.sign == b.sign && a.digits == b.digits);
- }
- 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;
- }
- }
- friend bool operator <= (const big_int& a, const big_int& b)
- {
- return (a < b || a == b);
- }
- friend bool operator >= (const big_int& a, const big_int& b)
- {
- return !(a < b);
- }
- big_int abs() const
- {
- big_int ans = *this;
- ans.sign = 1;
- return ans;
- }
- big_int operator - () const
- {
- if (digits == "0")
- return *this;
- big_int ans = *this;
- ans.sign *= -1;
- return ans;
- }
- 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;
- }
- }
- 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;
- }
- }
- 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;
- }
- 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;
- }
- big_int operator % (const big_int& b) const
- {
- return *this - *this / b * b;
- }
- 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;
- }
- 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;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement