题解：P1303 A*B Problem

· · 题解

用这篇题解纪念我们学校曾经花了一年时间学习高精度。

做法：

看起来这是很简单的题目，但是注意到：

每个非负整数不超过 10^{2000}。

非常大，传统的数据类型无法储存。

我们发现 Python 语言自带高精度，所以有如下 AC 代码：

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

可对于不自带高精度的 C++ 来说实在是太大了，就算是 long long 都无法储存，这时候就需要 C++ 的高精度算法了，输入不采用整数输入，而是使用字符串输入。

其流程类似于我们平时的竖式计算：

  1. 将输入的字符串的低位对齐，实现方法为将两个字符串倒序。
  2. 删除前导 0。
  3. 对每一位进行乘法。
  4. 进位并判断结果的位数。
  5. 倒序输出。

对于操作三，其原理为：

对于一个数，在这个数第 i 位（个位为第一位，十位为第二位，以此类推）上的一个数字 k 代表的值为 k \times 10^{i-1}，当两个数的某两位相乘时，式子形如 (k_1 \times 10^{i_1-1}) \times (k_2 \times 10^{i_2-1}) = k_1 \times k_2 \times 10^{i_1+i_2-2}，因为 k_1 \times k_2也要占位，所以第 i_1 位和第 i_2 位相乘会对结果的 i_1+i_2-1 项产生 k_1 \times k_2 贡献，最后记得向上进位。

因为之前输入时进行了倒序处理，所以输出时也需要倒序输出。

C++ 完整代码：

//大整数存储：    0下标存储个位数，
//      实现： 以字符串方式输入大整数，转换字符数组为数字数组，逆置数字数组
#include<iostream>
#include<cstring>
using namespace std;
char c1[10001],c2[10001];
int x[10005],y[10005],z[10001];

int main()
{

    //输入大整数到字符数组 
    cin>>c1>>c2;

    int len1=strlen(c1);
    int len2=strlen(c2);
    for(int i=0;i<len1;i++)
        x[i]=c1[i]-'0';
    for(int i=0;i<len2;i++)
        y[i]=c2[i]-'0';

    //逆置 
    for(int i=0;i<len1/2;i++)
        swap(x[i],x[len1-1-i]);
    for(int i=0;i<len2/2;i++)
        swap(y[i],y[len2-1-i]);

    //消除前导零
    for(int i=len1-1; i>0&&x[i]==0; len1--,i--);
    for(int i=len2-1; i>0&&y[i]==0; len2--,i--); 

    if(len1==1&&x[0]==0||len2==1&&y[0]==0)
    {
        cout<<0;
        return 0;
    }

    //乘法
    for(int i=0;i<len1;i++)
        for(int j=0;j<len2;j++)
        {
            z[i+j]+=x[i]*y[j];
            z[i+j+1]+=z[i+j]/10;
            z[i+j]=z[i+j]%10;//进位
        }

    //位数判断 
    int len=len1+len2;
    if(z[len-1]==0)
        len--;

    //输出大整数 
    for(int i=len-1;i>=0;i--)
        cout<<z[i]; 
}