题解：P1303 A*B Problem

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

做法：

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

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

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

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

PYTHON

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

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

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

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

对于操作三，其原理为：

对于一个数，在这个数第

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++ 完整代码：

CPP

//大整数存储：	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];	
}

题解：P1303 A*B Problem

文章操作

做法：

C++ 完整代码：

相关推荐

评论

题解：P1303 A*B Problem