题解：P1303 A*B Problem

P1303 $A \ast B$ Problem 题解

因为本题的数据范围是

0 \le A,B \le 10^{2000}

，

用 unsigned long long 直接乘也只能拿到40分。

所以就要使用高精度乘法计算解决本题。

高精度乘法

该算法是用字符串代替数字相乘的一种算法，在数据范围特别大的时候就能用到高精度乘法。

高精度乘法就是模拟~~小学3年级的~~笔算竖式乘法，具体操作如下：

输入两个字符串，将字符串转化成数字倒着存到数组里面。

CPP

cin>>s1>>s2;
int l1=s1.size(),l2=s2.size();
for(int i=1;i<=l1;i++){
  a[i]=s1[l1-i]-48; 
}
for(int i=1;i<=l2;i++){
  b[i]=s2[l2-i]-48;
}

将两个数组逐位相乘，不要有重复或漏乘。

CPP

for(int i=1;i<=l2;i++){ 
    for(int j=1;j<=l1;j++){
        c[i+j-1]+=a[j]*b[i];
    }
}

处理进位（ $c_i > 9$ ）的情况。

CPP

for(int i=1;i<l1+l2;i++){ 
    if(c[i]>9){
       c[i+1]+=c[i]/10;
       c[i]%=10;
    }
}

计算答案位数，除去答案的前导0。

CPP

l=l1+l2;
while(c[l]==0&&l>1){
      l--;
}

因为字符串转换成数字时是倒着进行转换，所以要倒序输出结果。

CPP

for(int i=l;i>=1;i--){
    cout<<c[i];
}

步骤梳理完了，现在就能获得本题的 AC 代码了。

AC Code

CPP

//写题解不易，管理员求过QAQ
#include<bits/stdc++.h>
using namespace std;
string s1,s2; //字符串数字
int a[10001],b[10001],x,l,c[10001]; 
int main (){
    cin>>s1>>s2;
    int l1=s1.size(),l2=s2.size();
    for(int i=1;i<=l1;i++){
        a[i]=s1[l1-i]-48; //每个数字字符转化数字储到数组里面
    }
    for(int i=1;i<=l2;i++){
        b[i]=s2[l2-i]-48;
    }
	for(int i=1;i<=l2;i++){ //逐位相乘
    	for(int j=1;j<=l1;j++){
        	c[i+j-1]+=a[j]*b[i];
        }
    }
    for(int i=1;i<l1+l2;i++){ //处理进位
    	if(c[i]>9){
            c[i+1]+=c[i]/10;
            c[i]%=10;
        }
    }
	l=l1+l2; //计算答案位数
    while(c[l]==0&&l>1){
        l--; //除去前导0
    }
    for(int i=l;i>=1;i--){ //倒序输出
        cout<<c[i];
    }
    return 0;
}

留在最后

刚学高精的萌新们，看完了我的题解，是不是感觉高精没有那么复杂了呢？那我们就一起学习编程知识，向着大牛的路出发！

题解：P1303 A*B Problem

文章操作

P1303 $A \ast B$ Problem 题解

高精度乘法

AC Code

留在最后

相关推荐

评论

题解：P1303 A*B Problem

文章操作

P1303 A∗BA \ast BA∗B Problem 题解

高精度乘法

AC Code

留在最后

相关推荐

评论

P1303 $A \ast B$ Problem 题解