高精度计算（Arbitrary-Precision Arithmetic），也被称作大整数（bignum）计算，运用了一些算法结构来支持更大整数间的运算（数字大小超过语言内建整型）。

先决条件

快读

C++重载运算符

高精度算法

模板题：洛谷 P1932 | A+B A-B A*B A/B A%B Problem

求 A、BA、B 的和差积商余！

题目描述

两个数两行

A BA \ B

输入格式

五个数

和 差 积 商 余

输出格式

输入输出样例

输入
1
2
1
1
输出
1
2
3
4
5
2
0
1
1
0

说明/提示

leng(A),leng(B)<=104leng(A),leng(B)<=10^4

A,B>0A,B>0 每个点 3s3s。

解决方案

原理

用数组模拟高精度类型，如1024可以表示成：

1
2
3
4
5
6
7
8
9
索引：
+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+

内容：
+---+---+---+---+---+
| 4 | 4 | 2 | 0 | 1 |
+---+---+---+---+---+

可知数组第 00 位存的是该大整数的位数，然后从个位依次往后存储每一位数字。

声明

由此可声明大整数类bigint如下：

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
class bigint
{
private:
    bool minus;
    int num[maxn];

public:
    bigint();
    bigint(const int &n);
    operator int() const;
    void read();
    void print() const;

    bool operator<(const bigint &x) const;
    bool operator<=(const bigint &x) const;
    bool operator!=(const bigint &x) const;
    bool operator==(const bigint &x) const;
    bool operator>(const bigint &x) const;
    bool operator>=(const bigint &x) const;

    bigint operator+(const bigint &x) const;
    bigint operator-() const;
    bigint operator-(const bigint &x) const;
    bigint operator*(const bigint &x) const;
    bigint operator/(const bigint &x) const;
    bigint operator%(const bigint &x) const;
    bigint operator=(const int &x);

    bigint abs() const;
};

输入输出

先是bigint类型的初始化和输入输出：

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
bigint::bigint()    //bigint初始化为正0
{
    minus = false;
    memset(num, 0, sizeof(num));
    num[0] = 1;
}

void bigint::read()
{
    memset(num, 0, sizeof(num));
    char s[maxn];
    scanf("%1s", s + 1);
    if (s[1] == '-')    //读入时先判断是不是负数
    {
        minus = true;
        scanf("%s", s + 1);
    }
    else
    {
        scanf("%s", s + 2);
    }
    num[0] = strlen(s + 1);
    for (int i = 1; i <= num[0]; i++)
    {
        num[i] = s[num[0] - i + 1] - '0';
    }
}

void bigint::print()
{
    if (minus)
        printf("-");
    for (int i = num[0]; i >= 1; i--)
    {
        printf("%d", num[i]);
    }
}

比较运算

由于高精度减法需要用到大整数的比较运算，不妨先写一下比较运算。比较运算看似有<， <=, !=, ==, >, >=这六类，但实际上只需要写<和==就可以了，原因如下：

类型 条件
<= <或==
> <的反向
>= >或==
!= <且>

因此只需要写好<和==的重载，其他比较运算符只需要调用已有接口即可。

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
bool bigint::operator<(const bigint &b) const
{
    if (minus != b.minus)
        return minus > b.minus;
    if (num[0] != b.num[0])
        return num[0] < b.num[0];
    for (int i = num[0]; i >= 1; i--)
    {
        if (num[i] != b.num[i])
            return num[i] <= b.num[i];
    }
    return false;
}

bool bigint::operator<=(const bigint &b) const
{
    if (*this < b || *this == b)
        return true;
    else
        return false;
}

bool bigint::operator!=(const bigint &b) const
{
    if (*this < b || b < *this)
        return true;
    else
        return false;
}

bool bigint::operator==(const bigint &b) const
{
    if (minus != b.minus)
        return false;
    if (num[0] != b.num[0])
        return false;
    for (int i = num[0]; i >= 1; i--)
    {
        if (num[i] != b.num[i])
            return false;
    }
    return true;
}

bool bigint::operator>=(const bigint &b) const
{
    if (b < *this || b == *this)
        return true;
    else
        return false;
}

bool bigint::operator>(const bigint &b) const
{
    if (b < *this)
        return true;
    else
        return false;
}

取绝对值、取相反数与强制类型转换

再顺便写一下取相反数，绝对值和int与bigint的互相转化。这里重载了int强制类型转换，同时对于int向bigint的转换，采取的 Modern C++所倡导的形如bigint(x)样式的显式转换，而非(bigint)x样式的传统 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
bigint::bigint(const int &n)
{
    int tmp = n;
    minus = tmp < 0;
    memset(num, 0, sizeof(num));
    while (tmp > 0)
    {
        num[++num[0]] = tmp % 10;
        tmp /= 10;
    }
    if (num[0] == 0)
        num[0] = 1;
}

bigint::operator int() const
{
    int n = 0;
    for (int i = num[0]; i >= 1; i--)
    {
        n *= 10;
        n += num[i];
    }
    return n;
}


bigint bigint::operator-() const
{
    bigint c = *this;
    c.minus ^= 1;
    return c;
}

bigint bigint::abs() const
{
    bigint c = *this;
    if (c < bigint(0))
        c = (-c);
    return c;
}

四则运算

至此正式写高精前的准备工作就完成了。

事实上高精度算法的本质是模拟人工列竖式计算的过程。如加法的做法是输入的两个数，按位相加，然后模拟进位即可。

然而不论加减乘除，我们都希望把复杂的情况转化为几种基本情况，比如加法中我们总是希望两个正数相加，减法中总是两个正数相减，且结果为正。

加法

对于加法来说，有这些情况：

  • a<0, b>0a < 0, \ b > 0 ，则 a+b=b−(−a))a + b = b - (-a))
  • a<0, b<0a < 0, \ b < 0 ，则 a+b=−((−a)+(−b))a + b = - ( (-a) + (-b) )
  • a>0, b>0a > 0, \ b > 0 ，则 a+b=a+ba + b = a + b
  • a>0, b<0a > 0, \ b < 0 ，则 a+b=a−(−b)a + b = a - (-b)
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
bigint bigint::operator+(const bigint &x) const
{

    if ((*this) == bigint(0))
        return x;
    if (x == bigint(0))
        return *this;

    if (*this < bigint(0) && x > bigint(0))
        return x - (*this).abs();
    if (*this < bigint(0) && x < bigint(0))
        return -((*this).abs() + x.abs());
    if (*this > bigint(0) && x < bigint(0))
        return (*this) - x.abs();

    bigint a = *this, b = x, c;
    c.num[0] = max(a.num[0], b.num[0]);
    for (int i = 1; i <= c.num[0]; i++)
    {
        c.num[i] += a.num[i] + b.num[i];
        c.num[i + 1] += c.num[i] / 10;
        c.num[i] %= 10;
    }
    if (c.num[c.num[0] + 1])
        c.num[0]++;
    return c;
}

减法

减法稍微复杂一点，我们应该尽量将其转换成两个正数的加减法操作，可以分几种情况判断：

  • a<0, b>0a < 0, \ b > 0 ，则 a−b=−((−a)+b)a - b = - ((-a) + b)
  • a<0, b<0a < 0, \ b < 0 ，则 a−b=(−b)−(−a)a - b = (-b) - (-a)
  • a>0, b>0a > 0, \ b > 0 ，则 a−b=a−ba - b = a - b
  • a>0, b<0a > 0, \ b < 0 ，则 a−b=a+(−b)a - b = a + (-b)
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
bigint bigint::operator-(const bigint &x) const
{
    bigint a = *this, b = x, c;
    if (a == bigint(0))
        return -b;
    if (b == bigint(0))
        return a;

    if (a < bigint(0) && b > bigint(0))
        return -(-a + b);
    if (a < bigint(0) && b < bigint(0))
        return (-b) - (-a);
    if (a > bigint(0) && b < bigint(0))
        return a + (-b);

    if (a < b)
    {
        c.minus ^= 1;
        swap(a, b);
    }

    c.num[0] = a.num[0];
    for (int i = 1; i <= c.num[0]; i++)
    {
        c.num[i] = a.num[i] - b.num[i];
    }
    for (int i = 1; i <= c.num[0]; i++)
    {
        if (c.num[i] < 0)
        {
            c.num[i + 1] -= 1;
            c.num[i] += 10;
        }
    }
    while (!c.num[c.num[0]])
    {
        if (c.num[0] == 1)
            break;
        c.num[0]--;
    }

    return c;
}

乘法

乘法需要注意的是，对于数 a, ba, \ b ， aa 的第 ii 位与 bb 的第 jj 之积对结果的第 i+j−1i + j - 1 位有贡献，计算过程中注意实时向第 i+ji + j 位进位。正负号方面， 符号不同为负，相同为正。

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
bigint bigint::operator*(const bigint &x) const
{
    bigint a = *this, b = x, c;
    if (a.abs() < b.abs())
        swap(a, b);
    c.minus = a.minus ^ b.minus;
    c.num[0] = a.num[0] + b.num[0];
    for (int j = 1; j <= b.num[0]; j++)
    {
        for (int i = 1; i <= a.num[0]; i++)
        {
            c.num[i + j - 1] += a.num[i] * b.num[j];
            c.num[i + j] += c.num[i + j - 1] / 10;
            c.num[i + j - 1] %= 10;
        }
    }
    while (!c.num[c.num[0]])
    {
        if (c.num[0] == 1)
        {
            c = bigint(0);
            break;
        }
        c.num[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
bigint bigint::operator/(const bigint &x) const
{
    bigint a = *this, b = x, c, tmp, cnt;
    bool flag = a.minus ^ b.minus;
    // c.minus = ;
    a = a.abs();
    b = b.abs();
    tmp.num[0] = a.num[0];
    tmp.num[tmp.num[0]] = 1;
    while (a > b)
    {
        cnt = bigint(0);
        while (b * tmp * (cnt + bigint(1)) <= a)
            cnt = cnt + bigint(1);
        c = c + tmp * cnt;
        a = a - b * tmp * cnt;
        tmp.num[tmp.num[0]] = 0;
        tmp.num[0]--;
        tmp.num[tmp.num[0]] = 1;
    }
    if (!(c.num[0] == 1 && c.num[1] == 0))
        c.minus = flag;
    return c;
}

取模

取模计算也很简单， bb 对 aa 取模的结果就是 a−⌊a/b⌋∗ba - \lfloor a / b \rfloor * b

1
2
3
4
5
bigint bigint::operator%(const bigint &x) const
{
    bigint a = *this, b = x;
    return a - a / b * b;
}

请参见