题解：P1303 A*B Problem

Zjb_nhzx_2021 · 2025-07-21 13:49:58 · 题解

P1303 A \ast B Problem 题解

因为本题的数据范围是 0 \le A,B \le 10^{2000}，

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

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

高精度乘法

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

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

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

   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;
   }

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

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

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

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

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

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

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

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

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

AC Code

//写题解不易，管理员求过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;
}

留在最后

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