四、高精度乘法

1、思路及模板

我们这里讲的高精度乘法为大整数 × \times × 小整数，大整数长度不超过 1 0 6 10^{6} 106，小整数数据范围不超过 1 0 9 10^{9} 109。

高精度乘法，就不只是单单的数学计算了，这里有些不同。

首先大数 a a a 倒序存储到 vector 中，这样也是为了方便进位，首先设定进位 t t t 。

再看一个例子，了解一下进位规则：

就比如这个例子，大数 a a a 的单独位数直接和 b b b 相乘，将结果累加到 t t t 中，将乘得的结果 % 10 \% 10 %10 存放到 c c c 数组中，然后 t / = 10 t /= 10 t/=10 ，将进位去掉一位 。其实这里的进位也很好理解，无非就是要让 t t t 到下一位，而下一位是当前位次 × 10 \times 10 ×10 ，所以 t t t 要前进一位就要 / 10 / 10 /10 。

这就是高精度乘法的运算规则，也不需要分类讨论啥的，就记住这个规律就好。虽然运算方法和我们从前计算方式有些不同，但是最终计算结果是相同的。

由于这个过程不太好画，所以不懂的小伙伴们可以下去自己模拟一下，操作很简单，但是用电脑画图不好表示。

模板 ：

vector<int> Mul(vector<int> &A, int b) 
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i++) {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (t) {
        C.push_back(t % 10);
        t /= 10;
    }
    // 去除前导 0 
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    return C;
}

我们再来讲讲模板里面的部分内容：

第一部分：

while (t) {
    C.push_back(t % 10);
    t /= 10;
}

这一部分就是在处理进位，因为运算结束之后，很可能还有进位没有处理。所以循环结束需要额外处理一下。

第二部分：

// 去除前导 0 
while (C.size() > 1 && C.back() == 0) {
    C.pop_back();
}

乘法也是会出现前导 0 0 0 的，比如任何一个数和 0 0 0 相乘结果都会是 0 0 0，所以这里也需要去一下前导 0 0 0 。

2、代码实现

链接：793. 高精度乘法

描述：

给定两个非负整数（不含前导 0 0 0 ） A A A 和 B B B ，请你计算 A × B A×B A×B 的值。

输入格式：

共两行，第一行包含整数 A A A ，第二行包含整数 B B B 。

输出格式：

共一行，包含 A × B A×B A×B 的值。

数据范围：

1 ≤ A 的长度 ≤ 100000 1≤A的长度≤100000 1≤A的长度≤100000

0 ≤ B ≤ 10000 0≤B≤10000 0≤B≤10000

输入样例：

2
3

输出样例：

6

由于上面我们基本上已经把代码讲过了，所以直接上代码，高精度乘法其实思路十分简单：

五、高精度除法

1、思路及模板

我们这里讲的高精度除法为大整数 / / / 小整数，大整数长度不超过 1 0 6 10^{6} 106，小整数数据范围不超过 1 0 9 10^{9} 109。

我们人在做除法时，会先看第一位，如果第一位大于除数，则在结果相应位置写下除以除数之后的数据，否则看下一位，这样以此类推。所以人算除法第一位都是有效数据位。

但是对于计算机不是这样，计算机则会默认从第一位算起，举个例子，比如 1234 / 11 1234 / 11 1234/11 ：如果以人的角度，第一位肯定为 1 1 1 ，但是计算机会从第一位开始看，第一位为 0 0 0 。

而 除法可能产生余数 ，所以还需要一个变量来记录余数。

有了这个概念，我们先看模板：

我们的模板是倒着存数据的，但是高精度除法是可以正着存的，因为除法需要从第一位开始除，所以正着存完全没有问题，但是之后可能会有高精度的混合运算，所以我们这边保持一致，也是倒着存。

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    return C;
}

看完模板之后，我们对里面的一些代码进行讲解 ：

第一块：

for (int i = A.size() - 1; i >= 0; i--) {
    r = r * 10 + A[i];
    C.push_back(r / b);
    r %= b;
}

首先看这一步，高精度除法比另外三个算法难的原因就是出在这一步上，因为运算规则可能不太好理解。

我们知道，如果要做除法运算，那么就需要一定的 补位 ，r * 10 + A[i] 就是在补位，因为下一次的需要被除的数据，就是第一次相除后的余数 × 10 \times 10 ×10 ，然后加上当前元素 A[i] 。

而除之后的结果就是 r / b r / b r/b ，每次除完都有相应的余数，所以 r %= b 。下面我们就用一张图演示一下：

通过这张图，我们就可以完美的解释代码究竟在干什么，实际上这就是一个计算的过程，过程涉及补位，相除，得余数等操作…

而最后，在进行完所有的操作之后 r r r 其实就是最终的余数。

第二块：

reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) {
    C.pop_back();
}

这两步就是在去前导 0 0 0 ，上面的图中我们也可以发现，高精度除法也是有前导 0 0 0 的，但是对于顺序表来说，前导 0 0 0不太好去，所以就逆置一下再去前导 0 0 0 。

最后倒着输出 c c c 即可。

2、代码实现

链接：794. 高精度除法

描述：

给定两个非负整数（不含前导 0 0 0 ） A ， B A，B A，B 请你计算 A / B A/B A/B 的商和余数。

输入格式：

共两行，第一行包含整数 A A A ，第二行包含整数 B B B 。

输出格式：

共两行，第一行输出所求的商，第二行输出所求余数。

数据范围：

1 ≤ A 的长度 ≤ 100000 1≤A的长度≤100000 1≤A的长度≤100000

1 ≤ B ≤ 10000 1≤B≤10000 1≤B≤10000

B B B 一定不为 0 0 0

输入样例：

7
2

输出样例：

3
1

思路我们说过了，接下来我把 倒着存 和 正着存 的两个版本都贴上来。

倒着存 ：

正着存：

六、结语

到这里，本篇文章就到此结束了，实际上高精度算法这一块还是很容易理解的，因为我们可以模拟它们计算的过程，所以对于一些细节不太了解的小伙伴们可以下去模拟一下。

一般来说，只要背过模板做这类问题就信手拈来了。所以不必担心嘿嘿。

当然，小伙伴们最好也找两道高精度问题练练手。我们不仅要看懂，还要会写。

如果觉得 a n d u i n anduin anduin 写的还不错的话，可以点赞 + 评论 + 收藏支持一下，我们下期见~