高精度乘法

一、算法描述

高精度加减法讨论的是两个大整数之间的运算。

而这里高精度乘除法讨论的是一个大整数和一个小整数之间的关系。

算法思路:

  • 还是模拟小学的乘法列竖式,只不过此时不太一样,原本的列竖式是一位一位的乘,这里需要改变一下思路。

  • 这里直接把小整数当成一个数,所乘的数直接当成进位参与运算即可。

  • 每次进位t += A[i] * b,然后将当前位数上的数(t % 10)加入答案数组,然后让t成为下一位的进位,t /= 10

  • 因为是乘法,所以会有可能超过很多位,我们需要把他们都加入答案数组而且不要忘了一位一位的加。

  • 如果一个很大的数乘 \(0\) 的话,那么会产生很多前导 \(0\) ,我们也需要处理一下。

经过优化之后代码如下:

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

二、题目描述

给定两个非负整数(不含前导 \(0\)\(A\)\(B\),请你计算 \(A×B\) 的值。

输入格式

共两行,第一行包含整数 \(A\),第二行包含整数 \(B\)

输出格式

共一行,包含 \(A × B\) 的值。

数据范围

\(1≤A的长度≤100000,\)
\(0≤B≤10000\)

输入样例:

2
3 

输出样例:

6 

三、题目来源

AcWing算法基础课-793.高精度乘法

四、源代码

#include <iostream>
#include <vector>

using namespace std;

const int N = 100010;

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;
    while (C.size() > 1 && C.back() == 0)   C.pop_back();
    
    return C;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;
    
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
    
    vector<int> C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
    
    return 0;
}

热门相关:重生之女将星   网游三国之城市攻略   上将大叔,狼来了!   一等狂妃:邪王,请接招!   我是仙凡