1 #include<bits/stdc++.h>
2
3 //大整数
4 struct BigInteger {
5 static const int BASE = 100000000;//和WIDTH保持一致
6 static const int WIDTH = 8;//八位一存储,如修改记得修改输出中的%08d
7 bool sign;//符号, 0表示负数
8 size_t length;
9 std::vector<int> num;//反序存
10 //构造函数
11 BigInteger(long long x = 0) { *this = x; }
12 BigInteger(const std::string &x) { *this = x; }
13 BigInteger(const BigInteger &x) { *this = x; }
14
15 //剪掉前导0
16 void cutLeadingZero() {
17 while (num.back() == 0 && num.size() != 1) { num.pop_back(); }
18 }
19
20 //设置数的长度
21 void setLength() {
22 cutLeadingZero();
23 int tmp = num.back();
24 if (tmp == 0) { length = 1; }
25 else {
26 length = (num.size() - 1) * WIDTH;
27 while (tmp > 0) {
28 ++length;
29 tmp /= 10;
30 }
31 }
32 }
33
34 //赋值运算符
35 BigInteger &operator=(long long x) {
36 num.clear();
37 if (x >= 0) sign = true;
38 else {
39 sign = false;
40 x = -x;
41 }
42 do {
43 num.emplace_back(x % BASE);
44 x /= BASE;
45 } while (x > 0);
46 setLength();
47 return *this;
48 }
49
50 //赋值运算符
51 BigInteger &operator=(const std::string &str) {
52 num.clear();
53 sign = (str[0] != '-');//设置符号
54 int x, len = (str.size() - 1 - (!sign)) / WIDTH + 1;
55 for (int i = 0; i < len; i++) {
56 int End = str.length() - i * WIDTH;
57 int start = std::max((int) (!sign), End - WIDTH);//防止越界
58 sscanf(str.substr(start, End - start).c_str(), "%d", &x);
59 num.push_back(x);
60 }
61 setLength();
62 return *this;
63 }
64
65 //赋值运算符
66 BigInteger &operator=(const BigInteger &tmp) {
67 num = tmp.num;
68 sign = tmp.sign;
69 length = tmp.length;
70 return *this;
71 }
72
73
74 //数的位数
75 size_t size() const { return length; }
76
77 //*10^n 除法中用到
78 BigInteger e(size_t n) const {
79 int tmp = n % WIDTH;
80 BigInteger ans;
81 ans.length = n + 1;
82 n /= WIDTH;
83 while (ans.num.size() <= n) ans.num.push_back(0);
84 ans.num[n] = 1;
85 while (tmp--) ans.num[n] *= 10;
86 return ans * (*this);
87 }
88
89 //绝对值
90 BigInteger abs() const {
91 BigInteger ans(*this);
92 ans.sign = true;
93 return ans;
94 }
95
96 //正号
97 const BigInteger &operator+() const { return *this; }
98
99 // + 运算符
100 BigInteger operator+(const BigInteger &b) const {
101 if (!b.sign) { return *this - (-b); }
102 if (!sign) { return b - (-*this); }
103 BigInteger ans;
104 ans.num.clear();
105 for (int i = 0, g = 0;; i++) {
106 if (g == 0 && i >= num.size() && i >= b.num.size()) break;
107 int x = g;
108 if (i < num.size()) x += num[i];
109 if (i < b.num.size()) x += b.num[i];
110 ans.num.push_back(x % BASE);
111 g = x / BASE;
112 }
113 ans.setLength();
114 return ans;
115 }
116
117 //负号
118 BigInteger operator-() const {
119 BigInteger ans(*this);
120 if (ans != 0) ans.sign = !ans.sign;
121 return ans;
122 }
123
124 // - 运算符
125 BigInteger operator-(const BigInteger &b) const {
126 if (!b.sign) { return *this + (-b); }
127 if (!sign) { return -((-*this) + b); }
128 if (*this < b) { return -(b - *this); }
129 BigInteger ans;
130 ans.num.clear();
131 for (int i = 0, g = 0;; i++) {
132 if (g == 0 && i >= num.size() && i >= b.num.size()) break;
133 int x = g;
134 g = 0;
135 if (i < num.size()) x += num[i];
136 if (i < b.num.size()) x -= b.num[i];
137 if (x < 0) {
138 x += BASE;
139 g = -1;
140 }
141 ans.num.push_back(x);
142 }
143 ans.setLength();
144 return ans;
145 }
146
147 // * 运算符
148 BigInteger operator*(const BigInteger &b) const {
149 int lena = num.size(), lenb = b.num.size();
150 std::vector<long long> ansLL;
151 for (int i = 0; i < lena + lenb; i++) ansLL.push_back(0);
152 for (int i = 0; i < lena; i++) {
153 for (int j = 0; j < lenb; j++) {
154 ansLL[i + j] += (long long) num[i] * (long long) b.num[j];
155 }
156 }
157 while (ansLL.back() == 0 && ansLL.size() != 1) ansLL.pop_back();
158 int len = ansLL.size();
159 long long g = 0, tmp;
160 BigInteger ans;
161 ans.sign = (ansLL.size() == 1 && ansLL[0] == 0) || (sign == b.sign);
162 ans.num.clear();
163 for (int i = 0; i < len; i++) {
164 tmp = ansLL[i];
165 ans.num.emplace_back((tmp + g) % BASE);
166 g = (tmp + g) / BASE;
167 }
168 if (g > 0) ans.num.emplace_back(g);
169 ans.setLength();
170 return ans;
171 }
172
173 // / 运算符 (大数除小数)
174 BigInteger operator/(const long long &b) const {
175 BigInteger c;
176 c.num.clear();
177 for (int i = 0; i < num.size(); i++) {
178 c.num.push_back(0);
179 }
180 long long g = 0;
181 for (int i = num.size() - 1; i >= 0; i--) {
182 c.num[i] = int((num[i] + g * BASE) / b);
183 g = num[i] + g * BASE - c.num[i] * b;
184 }
185 for (int i = num.size() - 1; c.num[i] == 0; i--) {
186 c.num.pop_back();
187 }
188 return c;
189 }
190
191 // /运算符 (大数除大数)
192 BigInteger operator/(const BigInteger &b) const {
193 BigInteger aa((*this).abs());
194 BigInteger bb(b.abs());
195 if (aa < bb) return 0;
196 char *str = new char[aa.size() + 1];
197 memset(str, 0, sizeof(char) * (aa.size() + 1));
198 BigInteger tmp;
199 int lena = aa.length, lenb = bb.length;
200 for (int i = 0; i <= lena - lenb; i++) {
201 tmp = bb.e(lena - lenb - i);
202 while (aa >= tmp) {
203 ++str[i];
204 aa = aa - tmp;
205 }
206 str[i] += '0';
207 }
208 BigInteger ans(str);
209 delete[]str;
210 ans.sign = (ans == 0 || sign == b.sign);
211 return ans;
212 }
213
214 // % 运算符 (大数取模小数)
215 BigInteger operator%(const long long &b) const {
216 long long ans = 0;
217 for (int i = num.size() - 1; i >= 0; i--)
218 ans = (ans * BASE + num[i]) % b;
219 return ans;
220 }
221
222 // %运算符 (大数取模大数)
223 BigInteger operator%(const BigInteger &b) const {
224 return *this - *this / b * b;
225 }
226
227 BigInteger &operator++() {
228 *this = *this + 1;
229 return *this;
230 } // ++ 运算符
231 BigInteger &operator--() {
232 *this = *this - 1;
233 return *this;
234 } // -- 运算符
235 BigInteger &operator+=(const BigInteger &b) {
236 *this = *this + b;
237 return *this;
238 } // += 运算符
239 BigInteger &operator-=(const BigInteger &b) {
240 *this = *this - b;
241 return *this;
242 } // -= 运算符
243 BigInteger &operator*=(const BigInteger &b) {
244 *this = *this * b;
245 return *this;
246 } // *=运算符
247 BigInteger &operator/=(const long long &b) {
248 *this = *this / b;
249 return *this;
250 } // /=运算符
251 BigInteger &operator/=(const BigInteger &b) {
252 *this = *this / b;
253 return *this;
254 } // /= 运算符
255 BigInteger &operator%=(const long long &b) {
256 *this = *this % b;
257 return *this;
258 } // %=运算符
259 BigInteger &operator%=(const BigInteger &b) {
260 *this = *this % b;
261 return *this;
262 } // %=运算符
263 // < 运算符
264 bool operator<(const BigInteger &b) const {
265 if (sign && !b.sign) { return false; }//正负
266 else if (!sign && b.sign) { return true; }//负正
267 else if (!sign && !b.sign) { return -b < -*this; }//负负
268 //正正
269 if (num.size() != b.num.size()) return num.size() < b.num.size();
270 for (int i = num.size() - 1; i >= 0; i--)
271 if (num[i] != b.num[i]) return num[i] < b.num[i];
272 return false;
273 }
274
275 bool operator>(const BigInteger &b) const { return b < *this; } // > 运算符
276 bool operator<=(const BigInteger &b) const { return !(b < *this); } // <= 运算符
277 bool operator>=(const BigInteger &b) const { return !(*this < b); } // >= 运算符
278 bool operator!=(const BigInteger &b) const { return b < *this || *this < b; } // != 运算符
279 bool operator==(const BigInteger &b) const { return !(b < *this) && !(*this < b); }//==运算符
280
281 bool operator||(const BigInteger &b) const { return *this != 0 || b != 0; } // || 运算符
282 bool operator&&(const BigInteger &b) const { return *this != 0 && b != 0; } // && 运算符
283 bool operator!() { return (bool) (*this == 0); } // ！ 运算符
284
285 //重载<<使得可以直接输出大数
286 friend std::ostream &operator<<(std::ostream &out, const BigInteger &x) {
287 if (!x.sign) out << '-';
288 out << x.num.back();
289 for (int i = x.num.size() - 2; i >= 0; i--) {
290 char buf[10];
291 //如WIDTH和BASR有变化,此处要修改为%0(WIDTH)d
292 sprintf(buf, "%08d", x.num[i]);
293 for (int j = 0; j < strlen(buf); j++) out << buf[j];
294 }
295 return out;
296 }
297
298 //重载>>使得可以直接输入大数
299 friend std::istream &operator>>(std::istream &in, BigInteger &x) {
300 std::string str;
301 in >> str;
302 size_t len = str.size();
303 int start = 0;
304 if (str[0] == '-') start = 1;
305 if (str[start] == '
