每周一算法：高精度乘法（二）大整数乘大整数-Toy模板网

这篇具有很好参考价值的文章主要介绍了每周一算法：高精度乘法（二）大整数乘大整数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

高精度乘法

高精度乘法是采用模拟算法对上百位甚至更多位的数字进行乘法运算。具体应用时一般分为两类：

大整数数乘整数
大整数乘大整数

算法思想

大整数乘大整数的基本思想是模拟竖式计中算多位数乘多位数，一般分为下面几步：

将乘数 $A$ 的每一位 $A_i$ 分别与乘数 $B$ 的每一位 $B_j$ 相乘，将结果累加到乘积 $C_{i+j}$ 位中
对乘积 $C$ 中的每一位 $C_i$ 进行进位处理
最后处理好多余的前导 $0$

下面以 $123\times89$ 为例模拟计算过程。

第一步，需要枚举乘数A的每一位 $A_i$ 与乘数B每一位 $B_j$ ，分别将它们相乘。

将 $A$ 的个位 $A_0=3$ 分别与 $B$ 的每一位 $B_j$ 相乘，将结果累加到乘积 $0$ 位和 $1$ 位中。
将 $A$ 的十位 $A_1=2$ 分别与 $B$ 的每一位 $B_j$ 相乘，将结果累加到乘积 $C$ 的对应位中。注意：此时是十位与 $B_j$ 相乘，因此在累加乘积时需要向左偏移1位，也就是累加到 $C_{1+j}$ 。
将 $A$ 的百位 $A_2=1$ 分别与 $B$ 的每一位 $B_j$ 相乘，将结果累加到乘积 $C$ 的对应位中。注意：此时是百位与 $B_j$ 相乘，因此在累加乘积时需要向左偏移2位，也就是累加到 $C_{2+j}$ 。

接着，将累加得到的乘积的每一位处理好进位，就得到最终的乘积了。
每周一算法：高精度乘法（二）大整数乘大整数
最后，如果乘积的高位有多余的 $0$ ，还需要将这些前导 $0$ 去掉。例如，乘数为0时，最终只需要保留 $1$ 个 $0$ 即可。

真题演练

[题目链接]P1303 A*B Problem

题目描述

给出两个非负整数，求它们的乘积。

输入格式

输入共两行，每行一个非负整数。

输出格式

输出一个非负整数表示乘积。

样例输入

1 
2

样例输出

提示

每个非负整数不超过 $10^{2000}$ 。文章来源地址https://www.toymoban.com/news/detail-413434.html

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> mul(vector<int> &a, vector<int> &b) {
    vector<int> c(a.size() + b.size(), 0); //初始化乘积c的大小，并默认填入0
    //模拟竖式乘法
    for(int i = 0; i < a.size(); i ++)
        for(int j = 0; j < b.size(); j ++) 
            c[i + j] += a[i] * b[j];
    //处理进位
    for(int i = 0; i < c.size() - 1; i ++)
    {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back(); //去掉前导0
    return c;
}
int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0'); 
    for(int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0'); 
    vector<int> C = mul(A, B);
    for(int i = C.size() - 1; i >= 0; i --) cout << C[i];
    return 0;
}