BigInt

1
BigInt a(10);

1
class BigInt {
2
public:
3
  BigInt() : sign(1) {}
4
  BigInt(const string &s) {
5
    int pos = 0;
6
    if (s[0] == '-') {
7
      sign = -1;
8
      pos = 1;
9
    } else
10
      sign = 1;
11
    for (int i = s.size(); i > pos; i -= base_digits) {
12
      int end = i;
13
      int start = max(pos, i - base_digits);
14
      int num = stoll(s.substr(start, end - start));
15
      digits.push_back(num);
16
    }
17
    trim();
18
  }
19
  BigInt(long long v) {
20
    if (v < 0) {
21
      sign = -1;
22
      v = -v;
23
    } else
24
      sign = 1;
25
    while (v > 0) {
26
      digits.push_back(v % base);
27
      v /= base;
28
    }
29
  }
30
  BigInt operator+(const BigInt &other) const {
31
    if (sign == other.sign) {
32
      BigInt result = *this;
33
      result.add(other);
34
      return result;
35
    } else
36
      return *this - (-other);
37
  }
38
  BigInt operator-(const BigInt &other) const {
39
    if (sign == other.sign)
40
      if (abs() >= other.abs()) {
41
        BigInt result = *this;
42
        result.subtract(other);
43
        return result;
44
      } else {
45
        BigInt result = other;
46
        result.subtract(*this);
47
        result.sign = -result.sign;
48
        return result;
49
      }
50
    else
51
      return *this + (-other);
52
  }
53
  BigInt operator*(const BigInt &other) const {
54
    BigInt result;
55
    result.digits.resize(digits.size() + other.digits.size());
56
    result.sign = sign * other.sign;
57
    for (size_t i = 0; i < digits.size(); ++i) {
58
      long long carry = 0;
59
      for (size_t j = 0; j < other.digits.size() || carry > 0; ++j) {
60
        long long cur = result.digits[i + j] + carry + digits[i] * 1LL * (j < other.digits.size() ? other.digits[j] : 0);
61
        carry = cur / base;
62
        result.digits[i + j] = cur % base;
63
      }
64
    }
65
    result.trim();
66
    return result;
67
  }
68
  BigInt &operator++() {
69
    *this = *this + BigInt(1);
70
    return *this;
71
  }
72
  BigInt operator++(signed) {
73
    BigInt temp = *this;
74
    ++(*this);
75
    return temp;
76
  }
77
  BigInt &operator--() {
78
    *this = *this - BigInt(1);
79
    return *this;
80
  }
81
  BigInt operator--(signed) {
82
    BigInt temp = *this;
83
    --(*this);
84
    return temp;
85
  }
86
  BigInt operator-() const {
87
    BigInt result = *this;
88
    if (!is_zero())
89
      result.sign = -result.sign;
90
    return result;
91
  }
92
  strong_ordering operator<=>(const BigInt &other) const {
93
    if (sign != other.sign)
94
      return sign <=> other.sign;
95
    return (sign == 1) ? abs_compare(other) : other.abs_compare(*this);
96
  }
97
  bool operator==(const BigInt &other) const { return (*this <=> other) == 0; }
98
  string to_string() const {
99
    string result = (sign == -1 ? "-" : "") + (digits.empty() ? "0" : std::to_string(digits.back()));
100
    for (int i = digits.size() - 2; i >= 0; --i)
101
      result += string(base_digits - std::to_string(digits[i]).length(), '0') + std::to_string(digits[i]);
102
    return result;
103
  }
104

105
private:
106
  vector<int> digits;
107
  int sign;
108
  static const int base = 1000000000000000000LL;
109
  static const int base_digits = 18;
110
  void add(const BigInt &other) {
111
    int carry = 0;
112
    for (size_t i = 0; i < other.digits.size() || carry > 0; ++i) {
113
      if (i == digits.size())
114
        digits.push_back(0);
115
      digits[i] += carry + (i < other.digits.size() ? other.digits[i] : 0);
116
      carry = digits[i] >= base;
117
      if (carry)
118
        digits[i] -= base;
119
    }
120
  }
121
  void subtract(const BigInt &other) {
122
    int borrow = 0;
123
    for (size_t i = 0; i < other.digits.size() || borrow > 0; ++i) {
124
      digits[i] -= borrow + (i < other.digits.size() ? other.digits[i] : 0);
125
      borrow = digits[i] < 0;
126
      if (borrow)
127
        digits[i] += base;
128
    }
129
    trim();
130
  }
131
  strong_ordering abs_compare(const BigInt &other) const {
132
    if (digits.size() != other.digits.size())
133
      return digits.size() <=> other.digits.size();
134
    for (int i = digits.size() - 1; i >= 0; --i)
135
      if (digits[i] != other.digits[i])
136
        return digits[i] <=> other.digits[i];
137
    return strong_ordering::equal;
138
  }
139
  BigInt abs() const {
140
    BigInt result = *this;
141
    result.sign = 1;
142
    return result;
143
  }
144
  bool is_zero() const { return digits.empty(); }
145
  void trim() {
146
    while (!digits.empty() && digits.back() == 0)
147
      digits.pop_back();
148
    if (digits.empty())
149
      sign = 1;
150
  }
151
};