高精度加、减、乘(高精乘高精)、除(高精除以高精)模板。

高精度加法

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
string add(string a, string b) {
int na[105], nb[105], nc[10005];

memset(na, 0, sizeof(na));
memset(nb, 0, sizeof(nb));
memset(nc, 0, sizeof(nc));

int lena = a.length(), lenb = b.length();
for (int i = 1; i <= lena; i++) na[i] = a[lena-i] - '0';
for (int i = 1; i <= lenb; i++) nb[i] = b[lenb-i] - '0';

for (int i = 1; i <= lena + lenb; i++) {
nc[i] += na[i] + nb[i];
if (nc[i] >= 10) {
nc[i+1]++;
nc[i] -= 10;
}
}

int lenc = lena + lenb + 1;
while (lenc > 0 && nc[--lenc] == 0);

char c[10005];
for (int i = lenc; i >= 1; i--) c[lenc-i] = nc[i] + '0';
return c;
}

高精度减法

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
string sub(string a, string b) {
int na[105], nb[105], nc[10005];

memset(na, 0, sizeof(na));
memset(nb, 0, sizeof(nb));
memset(nc, 0, sizeof(nc));

int lena = a.length(), lenb = b.length();
for (int i = 1; i <= lena; i++) na[i] = a[lena-i] - '0';
for (int i = 1; i <= lenb; i++) nb[i] = b[lenb-i] - '0';

for (int i = 1; i <= lena + lenb; i++) {
nc[i] += na[i] - nb[i];
if (nc[i] < 0) {
nc[i+1]--;
nc[i] += 10;
}
}

int lenc = lena + lenb + 1;
while (lenc > 0 && nc[--lenc] == 0);

char c[10005];
for (int i = lenc; i >= 1; i--) c[lenc-i] = nc[i] + '0';
return c;
}

高精度乘法

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
string mul(string a, string b) {
int na[105], nb[105], nc[10005];
int lena = a.length(), lenb = b.length();

memset(na, 0, sizeof(na));
memset(nb, 0, sizeof(nb));
memset(nc, 0, sizeof(nc));

for (int i = 1; i <= lena; i++)
na[i] = a[lena - i] - '0';
for (int i = 1; i <= lenb; i++)
nb[i] = b[lenb - i] - '0';

for (int i = 1; i <= lena; i++) {
for (int j = 1; j <= lenb; j++) {
nc[i+j-1] += na[i] * nb[j];
}
}

for (int i = 1; i < lena + lenb; i++) {
if (nc[i] >= 10) {
nc[i+1] += nc[i] / 10;
nc[i] %= 10;
}
}

int lenc = lena + lenb + 1;
while (nc[--lenc] == 0);

char c[10005];
for (int i = lenc; i >= 1; i--) c[lenc-i] = nc[i] + '0';
return c;
}

高精度除法

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
int cmp(int a[], int b[], int last, int len) {
if (a[last+len] != 0) return true; // 如果被除数的位数比除数大

// 逐位比较
for (int i = len; i > 0; i--) {
if (a[i+last-1] > b[i]) return true;
if (a[i+last-1] < b[i]) return false;
}

// 相等返回true
return true;
}

void div(string a, string b) {
// 声明变量
int lena = a.length(), lenb = b.length(), lenc = lena - lenb + 2, lend = max(lena, lenb) + 1;

// 清空变量
memset(na, 0, sizeof(na));
memset(nb, 0, sizeof(nb));
memset(nc, 0, sizeof(nc)); // 商
memset(nd, 0, sizeof(nd)); // 余数

// 把数字倒过来存
for (int i = 1; i <= lena; i++) na[i] = a[lena-i] - '0', nd[i] = na[i];
for (int i = 1; i <= lenb; i++) nb[i] = b[lenb-i] - '0';
//for (int i = 1; i <= lena; i++) nd[i] = na[i]; // 存余数

// 高精度除法
for (int i = lena - lenb + 1; i > 0; i--) { // 被除数和除数对齐
/* 456 / 12
* 38
* 12 |----
* 456
* 36
* ----
* 96
* 96
* ----
* 0
*/

// 可以相减
while (cmp(nd, nb, i, lenb)) {
// 高精度减法
for (int j = 1; j <= lenb; j++) {
nd[i+j-1] -= nb[j];
if (nd[i+j-1] < 0) {
nd[i+j]--;
nd[i+j-1] += 10;
}
}

nc[i]++; // 商进一位
}
}

// 输出商
while (nc[--lenc] == 0);
if (lenc <= 0) lenc++;
for (int i = lenc; i > 0; i--) {
cout << nc[i];
}

cout << endl;

// 输出余数
while (nd[--lend] == 0);
if (lend <= 0) lend++;
for (int i = lend; i > 0; i--) {
cout << nd[i];
}

cout << endl;
}

评论