题目描述

有两个用字符串表示的非常大的大整数,算出他们的乘积，也是用字符串表示。不能用系统自带的大整数类型。

输入描述:

空格分隔的两个字符串，代表输入的两个大整数

输出描述:

输入的乘积，用字符串表示

示例1

输入

72106547548473106236 982161082972751393

输出

70820244829634538040848656466105986748

 

思路

最直白的实现两数相乘的过程。。但要十分小心！进位那里太容易出错！

 

我提交的代码 

#include <string>
#include <iostream>
#include <vector>

int main(){
    std::string s1, s2;
    std::cin >> s1 >> s2;
    int len1 = s1.size();
    int len2 = s2.size();
    std::vector<int> rlt;
    std::string res;
    int offset = 0;
    for (int i = len1 - 1; i >= 0; --i){
        int val1 = s1[i] - '0';
        std::vector<int> temp;
        int carry = 0;
        for (int j = len2 - 1; j >= 0; --j){
            int val2 = s2[j] - '0';
            int p = val1 * val2;
            temp.push_back(p % 10 + carry);
            carry = p / 10;
        }
        if (carry != 0)
            temp.push_back(carry);
        
        carry = 0;
        if (rlt.empty()){
            for (int k = 0; k < temp.size(); ++k)
                rlt.push_back(temp[k]);
        }
        else{
            int rlt_size = rlt.size();
            for (int k = 0; k < temp.size(); ++k){
                if (k+offset <= rlt_size-1){
                    int add = temp[k] + rlt[k+offset] + carry;
                    rlt[k+offset] = add % 10;
                    carry = add / 10;
                }
                else{
                    rlt.push_back(carry + temp[k]);
                    carry = 0;
                }
            }
        }
        if (carry != 0)
            rlt.push_back(carry);
        offset++;
        carry = 0;
    }
    for (int k = rlt.size()-1; k >= 0; --k){
        std::string s = std::to_string(rlt[k]);
        res += s;
    }
    std::cout << res << std::endl;
        
    return 0;
}