| 1 | struct intx { |
| 2 | intx() { normalize(1); } |
| 3 | intx(string n) { init(n); } |
| 4 | intx(int n) { stringstream ss; ss << n; init(ss.str()); } |
| 5 | intx(const intx& other) |
| 6 | : sign(other.sign), data(other.data) { } |
| 7 | int sign; |
| 8 | vector<unsigned int> data; |
| 9 | static const int dcnt = 9; |
| 10 | static const unsigned int radix = 1000000000U; |
| 11 | int size() const { return data.size(); } |
| 12 | void init(string n) { |
| 13 | intx res; res.data.clear(); |
| 14 | if (n.empty()) n = "0"; |
| 15 | if (n[0] == '-') res.sign = -1, n = n.substr(1); |
| 16 | for (int i = n.size() - 1; i >= 0; i -= intx::dcnt) { |
| 17 | unsigned int digit = 0; |
| 18 | for (int j = intx::dcnt - 1; j >= 0; j--) { |
| 19 | int idx = i - j; |
| 20 | if (idx < 0) continue; |
| 21 | digit = digit * 10 + (n[idx] - '0'); } |
| 22 | res.data.push_back(digit); } |
| 23 | data = res.data; |
| 24 | normalize(res.sign); } |
| 25 | intx& normalize(int nsign) { |
| 26 | if (data.empty()) data.push_back(0); |
| 27 | for (int i = data.size() - 1; i > 0 && data[i] == 0; i--) |
| 28 | data.erase(data.begin() + i); |
| 29 | sign = data.size() == 1 && data[0] == 0 ? 1 : nsign; |
| 30 | return *this; } |
| 31 | friend ostream& operator <<(ostream& outs, const intx& n) { |
| 32 | if (n.sign < 0) outs << '-'; |
| 33 | bool first = true; |
| 34 | for (int i = n.size() - 1; i >= 0; i--) { |
| 35 | if (first) outs << n.data[i], first = false; |
| 36 | else { |
| 37 | unsigned int cur = n.data[i]; |
| 38 | stringstream ss; ss << cur; |
| 39 | string s = ss.str(); |
| 40 | int len = s.size(); |
| 41 | while (len < intx::dcnt) outs << '0', len++; |
| 42 | outs << s; } } |
| 43 | return outs; } |
| 44 | string to_string() const { |
| 45 | stringstream ss; ss << *this; return ss.str(); } |
| 46 | bool operator <(const intx& b) const { |
| 47 | if (sign != b.sign) return sign < b.sign; |
| 48 | if (size() != b.size()) |
| 49 | return sign == 1 ? size() < b.size() : size() > b.size(); |
| 50 | for (int i = size() - 1; i >= 0; i--) |
| 51 | if (data[i] != b.data[i]) |
| 52 | return sign == 1 ? data[i] < b.data[i] |
| 53 | : data[i] > b.data[i]; |
| 54 | return false; } |
| 55 | intx operator -() const { |
| 56 | intx res(*this); res.sign *= -1; return res; } |
| 57 | friend intx abs(const intx &n) { return n < 0 ? -n : n; } |
| 58 | intx operator +(const intx& b) const { |
| 59 | if (sign > 0 && b.sign < 0) return *this - (-b); |
| 60 | if (sign < 0 && b.sign > 0) return b - (-*this); |