大正整数乘法模板


前言

在日常竞赛刷题中,难免会遇到大整数乘法作为解题的中间步骤。

实现思路

首先,我们不难发现,两个数的乘积,其值的位数,不会大于这两个乘数位数之和。如99 * 99 = 9801

接下来,我们使用模拟手算乘法,如下图所示,不难发现,结果的第i + j 位,其实是两个乘数分别的第i位和第j位相乘

大整数乘法

之后,我们对每一次运算的结果进行处理,即如果运算结果是一位数,则直接进行累加,如果是两位数(如上图的81),则将高位的8累加到更高位,留下低位的1,如下图所示

大整数乘法

最后我们需要再对整个结果进行处理,使得每一位都数字都小于10,如下图所示

大整数乘法

具体实现方式

我们使用字符串类型来保存两个乘数

为了方便运算,我们设置三个整数向量,同时给两个向量用来存放两个乘数的逆序

接下来通过除法和取模运算,计算出每一个i + j 位的值,存到第三个向量中

然后我们对第三个向量进行除法和取模运算,保证每一位都是一个小于10的整数

最后我们把第三个向量转化为字符串,反转字符串,同时处理字符串第一位为0的情况

参考代码

#include<iostream>
using namespace std;
#include<vector>
#include<string>
vector<string>v;
void multiply(string a ,string b){
    string re  ;
    vector<int>an,bn,cn;
    for(int i = a.size() - 1 ; i >= 0 ; --i){an.push_back(a[i] - '0');}
    for(int i = b.size() - 1 ; i >= 0 ; --i){bn.push_back(b[i] - '0');}
    for(int i = 0 ; i < a.size() + b.size();++i) {cn.push_back(0);}

    for(int i = 0 ; i < a.size(); ++i){
        for(int j = 0; j < b.size() ; ++j){
             cn[i+j] += an[i]*bn[j] % 10;
             cn[i+j+1] += an[i]*bn[j] / 10;
        }
    }

    for(int i = 0 ; i < a.size() + b.size() ; ++i){
        cn[i+1] +=  cn[i]/10;
        cn[i]    =  cn[i]%10;
    }
    int len = 0 ;
    if(cn[a.size()+b.size()-1] == 0)  {len =a.size()+b.size()-2 ; }
    else                              {len = a.size()+b.size()-1;}
    for(int i = len; i >= 0 ; --i){
       cout<<cn[i];
    }
}

int main(){
   string a ,b;
   cin >>a >> b;
   multiply(a,b);
}

文章作者: 瑾年
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 瑾年 !
  目录