题目描述

一个大整数乘以一个小整数，输出他们的乘积

算法1 大整数* 大整数

乘法模拟

适用于大整数乘大整数

时间复杂度 o(m*n)

C++ 代码

#include<iostream>
#include<vector>
using namespace std;

void multi(const vector<int> &a, int val, vector<int> &c, int l){   //l是b的第几位
    int carry = 0;
    for(int i = 0; i < a.size(); ++i){
        carry += (a[i]*val);
        if(i+l >= c.size()) c.emplace_back(carry%10);     //判断一下有没有超过c的当前位数；
        else{
            carry += c[i+l];        //对于c来说要加上当前val在b中是第几位；
            c[i+l] = carry%10;
        }
        carry /= 10;
    }
    int len = a.size();          //len的存在是为了和l一起比较是否有超过c的当前长度；
    while(carry){               //处理当前进位仍存在的情况
        if(len+l >= c.size()) c.emplace_back(carry);
        else{
            carry += c[len+l];
            c[len+l] = carry%10;
        }
        carry /= 10;
        ++len;
    }
}

int main()
{
    string n1, n2;
    cin>>n1>>n2;
    if(n1=="0" || n2=="0"){cout<<0;return 0;}       //进行一个0乘的判定
    vector<int> a, b, c;
    for(int i = n1.size()-1; i >= 0; --i) a.emplace_back(n1[i]-'0');
    for(int i = n2.size()-1; i >= 0; --i) b.emplace_back(n2[i]-'0');

    for(int i = 0; i < b.size(); ++i)
        multi(a, b[i], c, i);
    for(int i = c.size()-1; i >= 0; --i)
        cout<<c[i];
    return 0;
}

算法2 y总的大整数乘小整数

时间复杂度 O(n)

C++ 代码

#include<iostream>
#include<vector>
using namespace std;

auto mul(const vector<int> &a, int b){       //const符限定不能对a进行更改，&减少内存消耗；
    vector<int> c; 
    int t = 0;
    for(int i = 0; i < a.size() || t; ++i){
        if(i < a.size()) t += a[i] * b;
        c.emplace_back(t%10);       //emplace_back()相较于push_back()少一个拷贝操作，因而优与push_back();
        t /= 10;
    }
    return c;
}

int main()
{
    string n;
    int b;
    cin>>n>>b;
    if(n == "0" || b == 0) {cout << 0; return 0;}       //判0乘
    vector<int> a;
    for(int i = n.size()-1; i >= 0; --i) a.emplace_back(n[i]-'0');
    auto c = mul(a, b);
    for(int i = c.size()-1; i >= 0; --i) cout<<c[i];
    return 0;
}