高精度模板

发表于 更新于 分类于 阅读次数： Disqus：

高精度加、减、乘（高精乘高精）、除（高精除以高精）模板。

高精度加法

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;
}