蓝桥杯 ADV-353 高精度乘法（试题解析）

试题 算法提高 高精度乘法

提交此题   评测记录  

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

计算机真是最傻的东西；他都不能计算大于10^65-1的a*b，请你帮这个“最傻”的东西过关，否则它就真的只认识1和0了。

输入格式

共两行；
第一行输入一个整数a；
第一行输入一个整数b。

输出格式

　　共一行，一个表示a*b的整数。

样例输入

2147483647
2147483647

样例输出

4611686014132420609

数据规模和约定

　　10^65-1<a,b<10^201-1

解题思路：模拟。

AC代码如下：

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

vector<int>    A;
vector<int>    B;
vector<int>    C;
string a,b;

void update(){
    
    for(int i=0;i<C.size();i++){
        if(C[i]>=10){
            if(i!=C.size()-1)    
                C[i+1]+=C[i]/10;
            else
                C.push_back(C[i]/10);
                
            C[i]%=10;
        }
    }
}

int main(int argc, char** argv) {
    cin>>a>>b;
    
    int Alen=a.size(),Blen=b.size();
    //获取a的高精度 向量 
    for(int i=Alen-1;i>=0;i--){
        int tmp=a[i]-'0';
        A.push_back(tmp);
    }
    
    //获取b的高精度 向量 
    for(int i=Blen-1;i>=0;i--){
        int tmp=b[i]-'0';
        B.push_back(tmp);
    }
    
    //A*B
    for(int i=0;i<Blen;i++){
        for(int j=0;j<Alen;j++){//B[i]* all elements in A
            if(i==0)
                C.push_back(A[j]*B[i]);
            else{
                if(j+i<C.size())
                    C[j+i]+=A[j]*B[i];
                else
                    C.push_back(A[j]*B[i]);
            }
                
        }
        //每乘以一次B[i],更新 C
        update();
    } 

    for(int i=C.size()-1;i>=0;i--){
        cout<<C[i];
    }

    return 0;
}