高精度加减乘模板

这是我将紫书上的高精度模板和 Menci 的高精度模板进行一定程度的修改得到的自己的板子。

其中要注意的是高精度减法需要均为正数,且大数减小数。如何比较大小?模板里面重载了 << 运算符,可以直接比较大小。

修改结构体中的 WIDTHBASE 可以达到修改压位的位数的目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
struct BigInt {
static const int BASE = 10000;
static const int WIDTH = 4;
int s[10005], n;

BigInt(long long num = 0) {*this = num;}
BigInt operator = (long long num) {
memset(s, 0, sizeof(s));
n = 0;
do{
s[++n] = num % BASE;
num /= BASE;
} while(num > 0);
return *this;
}
BigInt operator = (const string& str) {
memset(s, 0, sizeof(s));
n = 0;
int x, len = (str.length() - 1) / WIDTH + 1;
for(int i = 0; i < len; i++) {
int end = str.length() - i * WIDTH;
int start = max(0, end - WIDTH);
sscanf(str.substr(start, end - start).c_str(), "%d", &x);
s[++n] = x;
}
return *this;
}
BigInt operator + (const BigInt& b) const {
BigInt c;
memset(c.s, 0, sizeof(c.s));
c.n = 0;
for(int i = 1, g = 0; ; i++) {
if(g == 0 && i > n && i > b.n) break;
int x = g;
if(i <= n) x += s[i];
if(i <= b.n) x += b.s[i];
c.s[++c.n] = x % BASE;
g = x / BASE;
}
return c;
}
BigInt operator * (const BigInt& b) const {
BigInt c;
memset(c.s, 0, sizeof(c.s));
c.n = n + b.n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= b.n; j++) {
c.s[i + j - 1] += s[i] * b.s[j];
c.s[i + j] += c.s[i + j - 1] / BASE;
c.s[i + j - 1] %= BASE;
}
}
while(c.n > 1 && c.s[c.n] == 0) c.n--;
return c;
}
BigInt operator - (const BigInt& b) const {
BigInt c;
memset(c.s, 0, sizeof(c.s));
c.n = 0;
bool flag = false;
for(int i = 1; i <= n; i++) {
int x = s[i];
if(i <= b.n) x -= b.s[i];
if(flag) x--, flag = false;
if(x < 0) x += BASE, flag = true;
c.s[++c.n] = x;
}
while(c.n > 1 && c.s[c.n] == 0) c.n--;
return c;
}
bool operator < (const BigInt& b) const {
if(n != b.n) return n < b.n;
for(int i = n; i >= 1; i--)
if(s[i] != b.s[i]) return s[i] < b.s[i];
return false;
}
};

ostream& operator << (ostream& out, const BigInt& x) {
out << x.s[x.n];
for(int i = x.n - 1; i >= 1; i--) {
out << setw(4) << setfill('0') << x.s[i];
}
return out;
}

istream& operator >> (istream& in, BigInt& x) {
string s;
if(!(in >> s)) return in;
x = s;
return in;
}