【模板】高精度

class integer{
private:
	vector<int> digits;
	bool sign;
	void trim() { while (digits.size() > 1 && !digits.back()) digits.pop_back(); if (digits.size() == 1 && digits[0] == 0) sign = true; }
	bool absLess(const integer &b) const {if (digits.size() != b.digits.size()) return digits.size() < b.digits.size();for (int i = digits.size() - 1; i >= 0; i--) if (digits[i] != b.digits[i]) return digits[i] < b.digits[i];return false;}
public:
	integer() : sign(true) { digits.push_back(0); }
	integer(long long num) : sign(num >= 0) { if (!sign) num = -num; do { digits.push_back(num % 10); num /= 10; } while (num); }
	integer(const string &s) : sign(true) { int start = 0; if (s[0] == '-') { sign = false; start = 1; } digits.resize(s.length() - start); for (int i = s.length() - 1, j = 0; i >= start; i--, j++) digits[j] = s[i] - '0'; trim(); }
	integer& operator+=(const integer &b) { return *this = *this + b; }
	integer& operator-=(const integer &b) { return *this = *this - b; }
	integer& operator*=(const integer &b) { return *this = *this * b; }
	integer& operator/=(const integer &b) { return *this = *this / b; }
	integer& operator/=(long long b) { return *this = *this / b; }
	integer& operator%=(const integer &b) { return *this = *this % b; }
	integer operator+(const integer &b) const {if (sign != b.sign) return sign ? *this - (-b) : b - (-*this);integer res; res.digits.resize(max(digits.size(), b.digits.size()) + 1);for (int i = 0, carry = 0; i < res.digits.size(); i++) { int sum = carry + (i < digits.size() ? digits[i] : 0) + (i < b.digits.size() ? b.digits[i] : 0); res.digits[i] = sum % 10; carry = sum / 10; }res.sign = sign; res.trim(); return res;}
	integer operator-(const integer &b) const {if (sign != b.sign) return sign ? *this + (-b) : -(b + (-*this));if (absLess(b)) return -(b - *this);integer res; res.digits.resize(digits.size());for (int i = 0, borrow = 0; i < digits.size(); i++) { int diff = digits[i] - borrow - (i < b.digits.size() ? b.digits[i] : 0); borrow = diff < 0 ? 1 : 0; res.digits[i] = borrow ? diff + 10 : diff; }res.sign = sign; res.trim(); return res;}
	integer operator*(const integer &b) const {integer res; res.digits.resize(digits.size() + b.digits.size());for (int i = 0; i < digits.size(); i++) for (int j = 0, carry = 0; j < b.digits.size() || carry; j++) { long long product = res.digits[i + j] + digits[i] * 1LL * (j < b.digits.size() ? b.digits[j] : 0) + carry; res.digits[i + j] = product % 10; carry = product / 10; }res.sign = sign == b.sign; res.trim(); return res;}
	integer operator/(long long b) const {if (b == 0) throw runtime_error("Division by zero");bool resSign = (sign == (b > 0)); if (b < 0) b = -b;integer res; res.digits.resize(digits.size()); long long remainder = 0;for (int i = digits.size() - 1; i >= 0; i--) { remainder = remainder * 10 + digits[i]; res.digits[i] = remainder / b; remainder %= b; }res.sign = resSign; res.trim(); return res;}
	integer operator/(const integer &b) const {if (b.digits.size() == 1) return *this / (b.sign ? b.digits[0] : -b.digits[0]);if (absLess(b)) return integer(0);integer left(1), right = abs(), mid, res;while (!(left > right)) { mid = (left + right) / 2; if (mid * b <= abs()) { res = mid; left = mid + 1; } else right = mid - 1; }res.sign = sign == b.sign; return res;}
	integer operator%(const integer &b) const { return *this - (*this / b) * b; }
	integer operator-() const { integer res = *this; res.sign = !sign; return res; }
	integer abs() const { integer res = *this; res.sign = true; return res; }
	bool operator<(const integer &b) const { if (sign != b.sign) return !sign; return sign ? absLess(b) : b.absLess(*this); }
	bool operator>(const integer &b) const { return b < *this; }
	bool operator<=(const integer &b) const { return !(b < *this); }
	bool operator>=(const integer &b) const { return !(*this < b); }
	bool operator==(const integer &b) const { return sign == b.sign && digits == b.digits; }
	bool operator!=(const integer &b) const { return !(*this == b); }
	string toString() const { string s; for (int i = digits.size() - 1; i >= 0; i--) s += char(digits[i] + '0'); if (!sign) s = "-" + s; return s.empty() ? "0" : s; }
	friend ostream& operator<<(ostream &os, const integer &b) { os << b.toString(); return os; }
	friend istream& operator>>(istream &is, integer &b) { string s; is >> s; b = integer(s); return is; }
};