SolitudeAlma

今天我们来讲讲高精度乘法

什么是高精度乘法呢？

我们来看看百度百科什么介绍高精度乘法的，同样是因为存储数据的问题，大整数的乘法必定会有溢出的时候，那么我们应该怎么计算呢

其实乘法的计算也不难，我们这里会介绍高精度与高精度的乘法以及高精度与低精度的乘法，乘法我们用草稿纸演算的时候是按位相乘，就是一个数的每一位乘另一个数的每一位，然后再错位相加（注意不是数列求和的错位相加），还需注意前导零的情况，虽然乘法不会出现前导零，但是因为我们模板的原因，其中一个乘数为零是是会出现一堆零的，所以我们需要去掉多余的零

高精度乘低精度就很简单了，首先我们先把数字倒序存入数组中，然后用数组中的每一位去乘低精度的数对10取余存入结果数组，然后保留进位继续下一次计算，当然你可能会问万一乘出来的数用 unsigned long long 都存不了呢，我只能说这种情况只能用高精度乘高精度的模板了，而且既然题目的意思是高精度乘低精度就不会让你溢出

高精度乘高精度也不难，就是复现了草稿纸上的计算过程

我们直接上模板吧

// 高精度乘低精度
vector<int> mul(vector<int> &A , int b)
{
    vector<int> C;
    int t = 0;
    // 循环的判断是如果A算完了，但是最高位要进位需要再算一次，当然分离出去也行
    for(int i = 0; i < A.size() || t; i ++)
    {
        if(i < A.size()) t += A[i] * b; //if的判断配合循环判断
        C.push_back(t % 10); //模10就是我们要的结果
        t /= 10; // 保留进位
    }

    while(C.size() > 1 && C.back() == 0) C.pop_back(); //如果乘数为零则去前导零

    return C;
}

// 高精度乘高精度
vector<int> mul(vector<int> &A , vector<int> &B)
{
    vector<int> C(A.size() + B.size() , 0); //初始化，以免里面的数不是零，用于但是存相加的对应位结果

    int t = 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(); i ++)
    {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    // 去前导零，以免出现这种情况
    while(C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

接下来我们来一道模板题

AcWing 793.高精度乘法

题目描述

给定两个正整数A和B，请你计算A * B的值。

输入格式

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

输出格式

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

数据范围

$1≤A的长度≤100000,$

$0≤B≤10000$

输入样例：

2
3

输出样例：

C++代码

#include <iostream>
#include <vector>

using namespace std;

vector<int> A;
string a;
int b;

vector<int> mul(vector<int> &A , int b)
{
    vector<int> C;

    int t = 0;
    for(int i = 0; i < A.size() || t; i ++)
    {
        if(i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

int main()
{
    cin >> a  >> b;

    for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

    auto C = mul(A , b);

    for(int i = C.size() - 1; i >= 0; i --) cout << C[i];

    return 0;
}

引用

引用一些大佬的题解，其中有高精度乘高精度的模板，思路很不错orz，也有java的实现以及数组的实现

Anish AcWing 793. 高精度乘法 A x b 和 A x B 的模版

师大专升本16级学长 AcWing 793. 高精度乘法（C语言新手版）

小呆呆 AcWing 793. 高精度乘法

高精度乘法的介绍以及模板的分享