在运算过程中如果运算结果很大，普通的数据类型无法储存，就需要用到所谓的高精度算法，即用数组来存储整数，并模拟手算的方式进行四则运算。
First
Code
1#include <bits/stdc++.h>
2using namespace std;
3
4struct BigInteger {
5 static const int BASE = 100000000;
6 static const int WIDTH = 8;
7 vector<int> s;
8
9 BigInteger(long long num = 0) { *this = num; }
10 BigInteger& operator = (long long num) {
11 s.clear();
12 do {
13 s.push_back(num % BASE);
14 num /= BASE;
15 } while (num > 0);
16 return *this;
17 }
18 BigInteger& operator = (const string& str) {
19 s.clear();
20 int x, len = (str.length() - 1) / WIDTH + 1;
21 for(int i = 0; i < len; ++i){
22 int end = str.length() - i * WIDTH;
23 int start = max(0, end - WIDTH);
24 sscanf(str.substr(start, end-start).c_str(), "%d", &x);
25 s.push_back(x);
26 }
27 return *this;
28 }
29 friend ostream& operator << (ostream &out, const BigInteger& x){
30 out << x.s.back();
31 for(int i = x.s.size()-2; i >= 0; --i){
32 char buf[20];
33 sprintf(buf, "%08d", x.s[i]);
34 for(int j = 0; j < strlen(buf); ++j) out << buf[j];
35 }
36 return out;
37 }
38 friend istream& operator >> (istream &in, BigInteger& x){
39 string st;
40 if(!(in >> st)) return in;
41 x = st;
42 return in;
43 }
44 BigInteger operator + (const BigInteger& b) const{
45 BigInteger c;
46 c.s.clear();
47 for(int i = 0, g = 0; ; ++i){
48 if(g==0 && i>=s.size() && i>=b.s.size()) break;
49 int x = g;
50 if(i < s.size()) x += s[i];
51 if(i < b.s.size()) x += b.s[i];
52 c.s.push_back(x % BASE);
53 g = x / BASE;
54 }
55 return c;
56 }
57 BigInteger operator += (const BigInteger& b){
58 *this = *this + b; return *this;
59 }
60 bool operator < (const BigInteger& b) const {
61 if(s.size() != b.s.size()) return s.size() < b.s.size();
62 for(int i = s.size()-1; i >= 0; --i)
63 if(s[i] != b.s[i]) return s[i] < b.s[i];
64 return false;
65 }
66 bool operator > (const BigInteger& b) const { return b < *this; }
67 bool operator <= (const BigInteger& b) const { return !(b < *this); }
68 bool operator >= (const BigInteger& b) const { return !(*this < b); }
69 bool operator != (const BigInteger& b) const { return b < *this || *this < b; }
70 bool operator == (const BigInteger& b) const { return !(b < *this) && !(*this < b); }
71
72};
73int main() {
74 BigInteger a, b;
75 cin >> a >> b;
76 cout << "a= " << a << endl << "b= " << b << endl;
77 cout << "a+b= " << (a+b) << endl;
78 cout << "a<b " << (a<b) << endl;
79 cout << "a>b " << (a>b) << endl;
80 cout << "a<=b " << (a<=b) << endl;
81 cout << "a>=b " << (a>=b) << endl;
82 cout << "a!=b " << (a!=b) << endl;
83 cout << "a==b " << (a==b) << endl;
84 return 0;
85}
Second
Code
1#include <iostream>
2#include <cstdio>
3#include <cstdlib>
4#include <cstring>
5#include <string>
6#include <algorithm>
7
8using namespace std;
9
10const int MAXN = 410;
11
12struct BigInteger {
13 int len, s[MAXN];
14
15 BigInteger() {
16 memset(s, 0, sizeof(s));
17 len = 1;
18 }
19
20 BigInteger(int num) { *this = num; }
21
22 BigInteger(const char *num) { *this = num; }
23
24 BigInteger operator=(const int num) {
25 char s[MAXN];
26 sprintf(s, "%d", num);
27 *this = s;
28 return *this;
29 }
30
31 BigInteger operator=(const char *num) {
32 for (int i = 0; num[i] == '0'; num++); //去前导0
33 len = strlen(num);
34 for (int i = 0; i < len; i++) s[i] = num[len - i - 1] - '0';
35 return *this;
36 }
37
38 BigInteger operator+(const BigInteger &b) const //+
39 {
40 BigInteger c;
41 c.len = 0;
42 for (int i = 0, g = 0; g || i < max(len, b.len); i++) {
43 int x = g;
44 if (i < len) x += s[i];
45 if (i < b.len) x += b.s[i];
46 c.s[c.len++] = x % 10;
47 g = x / 10;
48 }
49 return c;
50 }
51
52 BigInteger operator+=(const BigInteger &b) {
53 *this = *this + b;
54 return *this;
55 }
56
57 void clean() {
58 while (len > 1 && !s[len - 1]) len--;
59 }
60
61 BigInteger operator*(const BigInteger &b) //*
62 {
63 BigInteger c;
64 c.len = len + b.len;
65 for (int i = 0; i < len; i++) {
66 for (int j = 0; j < b.len; j++) {
67 c.s[i + j] += s[i] * b.s[j];
68 }
69 }
70 for (int i = 0; i < c.len; i++) {
71 c.s[i + 1] += c.s[i] / 10;
72 c.s[i] %= 10;
73 }
74 c.clean();
75 return c;
76 }
77
78 BigInteger operator*=(const BigInteger &b) {
79 *this = *this * b;
80 return *this;
81 }
82
83 BigInteger operator-(const BigInteger &b) {
84 BigInteger c;
85 c.len = 0;
86 for (int i = 0, g = 0; i < len; i++) {
87 int x = s[i] - g;
88 if (i < b.len) x -= b.s[i];
89 if (x >= 0) g = 0;
90 else {
91 g = 1;
92 x += 10;
93 }
94 c.s[c.len++] = x;
95 }
96 c.clean();
97 return c;
98 }
99
100 BigInteger operator-=(const BigInteger &b) {
101 *this = *this - b;
102 return *this;
103 }
104
105 BigInteger operator/(const BigInteger &b) {
106 BigInteger c, f = 0;
107 for (int i = len - 1; i >= 0; i--) {
108 f = f * 10;
109 f.s[0] = s[i];
110 while (f >= b) {
111 f -= b;
112 c.s[i]++;
113 }
114 }
115 c.len = len;
116 c.clean();
117 return c;
118 }
119
120 BigInteger operator/=(const BigInteger &b) {
121 *this = *this / b;
122 return *this;
123 }
124
125 BigInteger operator%(const BigInteger &b) {
126 BigInteger r = *this / b;
127 r = *this - r * b;
128 return r;
129 }
130
131 BigInteger operator%=(const BigInteger &b) {
132 *this = *this % b;
133 return *this;
134 }
135
136 bool operator<(const BigInteger &b) {
137 if (len != b.len) return len < b.len;
138 for (int i = len - 1; i >= 0; i--) {
139 if (s[i] != b.s[i]) return s[i] < b.s[i];
140 }
141 return false;
142 }
143
144 bool operator>(const BigInteger &b) {
145 if (len != b.len) return len > b.len;
146 for (int i = len - 1; i >= 0; i--) {
147 if (s[i] != b.s[i]) return s[i] > b.s[i];
148 }
149 return false;
150 }
151
152 bool operator==(const BigInteger &b) {
153 return !(*this > b) && !(*this < b);
154 }
155
156 bool operator!=(const BigInteger &b) {
157 return !(*this == b);
158 }
159
160 bool operator<=(const BigInteger &b) {
161 return *this < b || *this == b;
162 }
163
164 bool operator>=(const BigInteger &b) {
165 return *this > b || *this == b;
166 }
167
168 string str() const {
169 string res = "";
170 for (int i = 0; i < len; i++) res = char(s[i] + '0') + res;
171 return res;
172 }
173};
174
175istream &operator>>(istream &in, BigInteger &x) {
176 string s;
177 in >> s;
178 x = s.c_str();
179 return in;
180}
181
182ostream &operator<<(ostream &out, const BigInteger &x) {
183 out << x.str();
184 return out;
185}
186
187int main() {
188 BigInteger a, b, c, d, e, f, g;
189 while (cin >> a >> b) {
190 a.clean(), b.clean();
191 c = a + b;
192 d = a - b;
193 e = a * b;
194 f = a / b;
195 g = a % b;
196 cout << "a+b" << "=" << c << endl; // a += b
197 cout << "a-b" << "=" << d << endl; // a -= b;
198 cout << "a*b" << "=" << e << endl; // a *= b;
199 cout << "a/b" << "=" << f << endl; // a /= b;
200 cout << "a%b" << "=" << g << endl; // a %= b;
201 if (a != b) printf("YES\n");
202 else printf("NO\n");
203 }
204 return 0;
205}
Third (The most complete)
Code
1#include <bits/stdc++.h>
2using namespace std;
3// base and base_digits must be consistent
4constexpr int base = 1000000000;
5constexpr int base_digits = 9;
6
7struct bigint {
8 // value == 0 is represented by empty z
9 vector<int> z; // digits
10
11 // sign == 1 <==> value >= 0
12 // sign == -1 <==> value < 0
13 int sign;
14
15 bigint() : sign(1) {}
16 bigint(long long v) { *this = v; }
17
18 bigint &operator=(long long v) {
19 sign = v < 0 ? -1 : 1; v *= sign;
20 z.clear(); for (; v > 0; v = v / base) z.push_back((int) (v % base));
21 return *this;
22 }
23
24 bigint(const string &s) { read(s); }
25
26 bigint &operator+=(const bigint &other) {
27 if (sign == other.sign) {
28 for (int i = 0, carry = 0; i < other.z.size() || carry; ++i) {
29 if (i == z.size())
30 z.push_back(0);
31 z[i] += carry + (i < other.z.size() ? other.z[i] : 0);
32 carry = z[i] >= base;
33 if (carry)
34 z[i] -= base;
35 }
36 } else if (other != 0 /* prevent infinite loop */) {
37 *this -= -other;
38 }
39 return *this;
40 }
41
42 friend bigint operator+(bigint a, const bigint &b) { return a += b; }
43
44 bigint &operator-=(const bigint &other) {
45 if (sign == other.sign) {
46 if (sign == 1 && *this >= other || sign == -1 && *this <= other) {
47 for (int i = 0, carry = 0; i < other.z.size() || carry; ++i) {
48 z[i] -= carry + (i < other.z.size() ? other.z[i] : 0);
49 carry = z[i] < 0;
50 if (carry)
51 z[i] += base;
52 }
53 trim();
54 } else {
55 *this = other - *this;
56 this->sign = -this->sign;
57 }
58 } else {
59 *this += -other;
60 }
61 return *this;
62 }
63
64 friend bigint operator-(bigint a, const bigint &b) { return a -= b; }
65
66 bigint &operator*=(int v) {
67 if (v < 0) sign = -sign, v = -v;
68 for (int i = 0, carry = 0; i < z.size() || carry; ++i) {
69 if (i == z.size())
70 z.push_back(0);
71 long long cur = (long long) z[i] * v + carry;
72 carry = (int) (cur / base);
73 z[i] = (int) (cur % base);
74 }
75 trim();
76 return *this;
77 }
78
79 bigint operator*(int v) const { return bigint(*this) *= v; }
80
81 friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
82 int norm = base / (b1.z.back() + 1);
83 bigint a = a1.abs() * norm;
84 bigint b = b1.abs() * norm;
85 bigint q, r;
86 q.z.resize(a.z.size());
87
88 for (int i = (int) a.z.size() - 1; i >= 0; i--) {
89 r *= base;
90 r += a.z[i];
91 int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
92 int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
93 int d = (int) (((long long) s1 * base + s2) / b.z.back());
94 r -= b * d;
95 while (r < 0)
96 r += b, --d;
97 q.z[i] = d;
98 }
99
100 q.sign = a1.sign * b1.sign;
101 r.sign = a1.sign;
102 q.trim();
103 r.trim();
104 return {q, r / norm};
105 }
106
107 friend bigint sqrt(const bigint &a1) {
108 bigint a = a1;
109 while (a.z.empty() || a.z.size() % 2 == 1)
110 a.z.push_back(0);
111
112 int n = a.z.size();
113
114 int firstDigit = (int) ::sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
115 int norm = base / (firstDigit + 1);
116 a *= norm;
117 a *= norm;
118 while (a.z.empty() || a.z.size() % 2 == 1)
119 a.z.push_back(0);
120
121 bigint r = (long long) a.z[n - 1] * base + a.z[n - 2];
122 firstDigit = (int) ::sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
123 int q = firstDigit;
124 bigint res;
125
126 for (int j = n / 2 - 1; j >= 0; j--) {
127 for (;; --q) {
128 bigint r1 = (r - (res * 2 * base + q) * q) * base * base +
129 (j > 0 ? (long long) a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
130 if (r1 >= 0) {
131 r = r1;
132 break;
133 }
134 }
135 res *= base;
136 res += q;
137
138 if (j > 0) {
139 int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
140 int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
141 int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
142 q = (int) (((long long) d1 * base * base + (long long) d2 * base + d3) / (firstDigit * 2));
143 }
144 }
145
146 res.trim();
147 return res / norm;
148 }
149
150 bigint operator/(const bigint &v) const { return divmod(*this, v).first; }
151
152 bigint operator%(const bigint &v) const { return divmod(*this, v).second; }
153
154 bigint &operator/=(int v) {
155 if (v < 0) sign = -sign, v = -v;
156 for (int i = (int) z.size() - 1, rem = 0; i >= 0; --i) {
157 long long cur = z[i] + rem * (long long) base;
158 z[i] = (int) (cur / v);
159 rem = (int) (cur % v);
160 }
161 trim();
162 return *this;
163 }
164
165 bigint operator/(int v) const { return bigint(*this) /= v; }
166
167 int operator%(int v) const {
168 if (v < 0) v = -v;
169 int m = 0;
170 for (int i = (int) z.size() - 1; i >= 0; --i)
171 m = (int) ((z[i] + m * (long long) base) % v);
172 return m * sign;
173 }
174
175 bigint &operator*=(const bigint &v) { return *this = *this * v; }
176 bigint &operator/=(const bigint &v) { return *this = *this / v; }
177
178 bool operator<(const bigint &v) const {
179 if (sign != v.sign)
180 return sign < v.sign;
181 if (z.size() != v.z.size())
182 return z.size() * sign < v.z.size() * v.sign;
183 for (int i = (int) z.size() - 1; i >= 0; i--)
184 if (z[i] != v.z[i])
185 return z[i] * sign < v.z[i] * sign;
186 return false;
187 }
188
189 bool operator>(const bigint &v) const { return v < *this; }
190 bool operator<=(const bigint &v) const { return !(v < *this); }
191 bool operator>=(const bigint &v) const { return !(*this < v); }
192
193 bool operator==(const bigint &v) const { return !(*this < v) && !(v < *this); }
194
195 bool operator!=(const bigint &v) const { return *this < v || v < *this; }
196
197 void trim() {
198 while (!z.empty() && z.back() == 0) z.pop_back();
199 if (z.empty()) sign = 1;
200 }
201
202 bool isZero() const { return z.empty(); }
203
204 friend bigint operator-(bigint v) {
205 if (!v.z.empty()) v.sign = -v.sign;
206 return v;
207 }
208
209 bigint abs() const {
210 return sign == 1 ? *this : -*this;
211 }
212
213 long long longValue() const {
214 long long res = 0;
215 for (int i = (int) z.size() - 1; i >= 0; i--)
216 res = res * base + z[i];
217 return res * sign;
218 }
219
220 friend bigint gcd(const bigint &a, const bigint &b) {
221 return b.isZero() ? a : gcd(b, a % b);
222 }
223
224 friend bigint lcm(const bigint &a, const bigint &b) {
225 return a / gcd(a, b) * b;
226 }
227
228 void read(const string &s) {
229 sign = 1;
230 z.clear();
231 int pos = 0;
232 while (pos < s.size() && (s[pos] == '-' || s[pos] == '+')) {
233 if (s[pos] == '-')
234 sign = -sign;
235 ++pos;
236 }
237 for (int i = (int) s.size() - 1; i >= pos; i -= base_digits) {
238 int x = 0;
239 for (int j = max(pos, i - base_digits + 1); j <= i; j++)
240 x = x * 10 + s[j] - '0';
241 z.push_back(x);
242 }
243 trim();
244 }
245
246 friend istream &operator>>(istream &stream, bigint &v) {
247 string s; stream >> s;
248 v.read(s);
249 return stream;
250 }
251
252 friend ostream &operator<<(ostream &stream, const bigint &v) {
253 if (v.sign == -1)
254 stream << '-';
255 stream << (v.z.empty() ? 0 : v.z.back());
256 for (int i = (int) v.z.size() - 2; i >= 0; --i)
257 stream << setw(base_digits) << setfill('0') << v.z[i];
258 return stream;
259 }
260
261 static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
262 vector<long long> p(max(old_digits, new_digits) + 1);
263 p[0] = 1;
264 for (int i = 1; i < p.size(); i++)
265 p[i] = p[i - 1] * 10;
266 vector<int> res;
267 long long cur = 0;
268 int cur_digits = 0;
269 for (int v : a) {
270 cur += v * p[cur_digits];
271 cur_digits += old_digits;
272 while (cur_digits >= new_digits) {
273 res.push_back(int(cur % p[new_digits]));
274 cur /= p[new_digits];
275 cur_digits -= new_digits;
276 }
277 }
278 res.push_back((int) cur);
279 while (!res.empty() && res.back() == 0)
280 res.pop_back();
281 return res;
282 }
283
284 typedef vector<long long> vll;
285
286 static vll karatsubaMultiply(const vll &a, const vll &b) {
287 int n = a.size();
288 vll res(n + n);
289 if (n <= 32) {
290 for (int i = 0; i < n; i++)
291 for (int j = 0; j < n; j++)
292 res[i + j] += a[i] * b[j];
293 return res;
294 }
295
296 int k = n >> 1;
297 vll a1(a.begin(), a.begin() + k);
298 vll a2(a.begin() + k, a.end());
299 vll b1(b.begin(), b.begin() + k);
300 vll b2(b.begin() + k, b.end());
301
302 vll a1b1 = karatsubaMultiply(a1, b1);
303 vll a2b2 = karatsubaMultiply(a2, b2);
304
305 for (int i = 0; i < k; i++)
306 a2[i] += a1[i];
307 for (int i = 0; i < k; i++)
308 b2[i] += b1[i];
309
310 vll r = karatsubaMultiply(a2, b2);
311 for (int i = 0; i < a1b1.size(); i++)
312 r[i] -= a1b1[i];
313 for (int i = 0; i < a2b2.size(); i++)
314 r[i] -= a2b2[i];
315
316 for (int i = 0; i < r.size(); i++)
317 res[i + k] += r[i];
318 for (int i = 0; i < a1b1.size(); i++)
319 res[i] += a1b1[i];
320 for (int i = 0; i < a2b2.size(); i++)
321 res[i + n] += a2b2[i];
322 return res;
323 }
324
325 bigint operator*(const bigint &v) const {
326 vector<int> a6 = convert_base(this->z, base_digits, 6);
327 vector<int> b6 = convert_base(v.z, base_digits, 6);
328 vll a(a6.begin(), a6.end());
329 vll b(b6.begin(), b6.end());
330 while (a.size() < b.size())
331 a.push_back(0);
332 while (b.size() < a.size())
333 b.push_back(0);
334 while (a.size() & (a.size() - 1))
335 a.push_back(0), b.push_back(0);
336 vll c = karatsubaMultiply(a, b);
337 bigint res;
338 res.sign = sign * v.sign;
339 for (int i = 0, carry = 0; i < c.size(); i++) {
340 long long cur = c[i] + carry;
341 res.z.push_back((int) (cur % 1000000));
342 carry = (int) (cur / 1000000);
343 }
344 res.z = convert_base(res.z, 6, base_digits);
345 res.trim();
346 return res;
347 }
348
349};
350
351bigint random_bigint(int n) {
352 string s;
353 for (int i = 0; i < n; i++) {
354 s += rand() % 10 + '0';
355 }
356 return bigint(s);
357}
358
359// random tests
360void bigintTest() {
361 bigint x = bigint("120");
362 bigint y = bigint("5");
363 cout << x / y << endl;
364
365 for (int i = 0; i < 1000; i++) {
366 int n = rand() % 100 + 1;
367 bigint a = random_bigint(n);
368 bigint res = sqrt(a);
369 bigint xx = res * res;
370 bigint yy = (res + 1) * (res + 1);
371
372 if (xx > a || yy <= a) {
373 cout << i << endl;
374 cout << a << " " << res << endl;
375 break;
376 }
377
378 int m = rand() % n + 1;
379 bigint b = random_bigint(m) + 1;
380 res = a / b;
381 xx = res * b;
382 yy = b * (res + 1);
383
384 if (xx > a || yy <= a) {
385 cout << i << endl;
386 cout << a << " " << b << " " << res << endl;
387 break;
388 }
389 }
390
391 bigint a = random_bigint(10000);
392 bigint b = random_bigint(2000);
393 clock_t start = clock();
394 bigint c = a / b;
395 printf("time=%.3lfsec\n", (clock() - start) * 1. / CLOCKS_PER_SEC);
396}
397
398string str(bigint b) {
399 stringstream ss; ss << b;
400 string s; ss >> s;
401 return s;
402}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。