A3 高精度乘法 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P1303 ↗

题目描述

高精度乘法模板题。

输入格式

两个非负整数 a,b，求它们的乘积。

输出格式

输出一个非负整数表示乘积。每个非负整数不超过 $10^{2000}$

输入输出样例

输入 #1

2
1

plaintext

输出 #1

plaintext

算法解析#

高精度计算实际上用数组存储和模拟运算。

高精度乘法的步骤：

高精度数字利用字符串读入；
把字符串翻转存入两个整型数组 A,B；
从低位到高位，累加乘积，进位，存余；
把数组 C 从高位到低位依次输出。

时间复杂度O( $n^{2}$ )

Python代码实现#

a = int(input())
b = int(input())
print(a * b)

python

C++代码实现#

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=4001;
int a[N],b[N],c[N];
int la,lb,lc;

void mul(int a[],int b[],int c[]){ //a*b=c
    for(int i=1;i<=la;i++)
        for(int j=1;j<=lb;j++)
            c[i+j-1]+=a[i]*b[j]; //存乘积

    for(int i=1;i<lc;i++){
        c[i+1]+=c[i]/10;  //存进位
        c[i]%=10;         //存余数
    }
    while(c[lc]==0&&lc>1) lc--; //去0
}
int main(){
    char A[N],B[N];
    cin>>A>>B;
    la=strlen(A); lb=strlen(B); lc=la+lb;
    for(int i=1;i<=la;i++)a[i]=A[la-i]-'0';
    for(int i=1;i<=lb;i++)b[i]=B[lb-i]-'0';
    mul(a,b,c);
    for(int i=lc;i>=1;i--) cout<<c[i];
    return 0;
}