题目描述

原题

题目大意&链接

给定两个正整数，计算高精度整数乘以低精度整数。

输入输出样例：
输入：

2
3

输出：

6

详情：ac_793高精度乘法

解题思路

高精度乘法需要注意2点。

  1. 计算机处理乘法是将被乘数的每一位乘以乘数，然后赋值给进位 t ，t%10 作结果的数值位，t/10作进位： 
    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;
    }
  2. 去除结果的前导0： 
    while(c.size() > 1 && c.back() == 0) c.pop_back();  //去除结果的前导0

完整代码

#include<iostream>
#include<vector>

using namespace std;

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();  //去除结果的前导0
    
    return c;
}

int main()
{
    string a;
    int b;
    vector<int> A;
    
    //高精度整数乘以低精度整数
    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--) printf("%d", c[i]);
}

时间和空间复杂度

假设 a 和 b 的长度分别为 n 和 m，则：
时间复杂度：O(n + m)
空间复杂度：O(n + m)