T226689 求两个正整数的乘积

题目描述

给你两个正整数 \(A\) 和 \(B\)，\((1<=A，B<=10^{2000})\)。求 \(A\) 与 \(B\) 的乘积。

输入格式

包括一行，两个正整数\(A\) 和 \(B\)，\((1<=A，B<=10^{2000})\)。

输出格式

一行，一个正整数表示乘积。

样例 #1

样例输入 #1

3 7

样例输出 #1

21

代码及其思路

由题A，B两数的范围可达到\(10^{2000}\)这个量级，所以选择使用高精度算法
而高精度算法就是对竖式乘法的模拟
例如:
\(\qquad\quad 2\ 9\ 3\ 4\)
\(\times\quad\quad \ 3\ 4\ 8\ 9\)
\(———————\)
\(\quad\quad\ 2\ 6\ 4\ 0\ 6\)
\(\quad\ \ 2\ 3\ 4\ 7\ 2\ 0\)
\(\ \ \ 1\ 1\ 7\ 3\ 4\ 0\ 0\)
\(\ \ \ 8\ 8\ 0\ 2\ 0\ 0\ 0\)
\(———————\)
\(1\ 0\ 2\ 3\ 6\ 7\ 2\ 6\)
我们的目的就是模拟上述竖式的计算过程

输入处理

由于需要对每一位进行处理，所以以字符串存储每一位然后转换成整型数组方便处理
由于需要以个位对齐，所以转换成整型数组的同时反转数组

高精度过程

进行竖式乘法可以先不考虑进位
显然，竖式计算时需要双重循环，外层循环i为\(B\)（即例中的3489），内层循环j为\(A\)
同时存入答案数组c，有如下公式c[i + j - 1] += a[j] * b[i]
即\(A\)的第j位乘以\(B\)的第i位应存入答案数\(C\)的第i+j-1中，实现错位相加

进位

对答案数组进行循环i，如果第i位数字大于9，先进位后取个位

输出处理

记\(A\)，\(B\)位数分别为lena，lenb
由于输入处理时反转了数组，而结果位数不超过两数位数之和即lena+lenb，所以输出时从lena+lenb开始反向输出，同时去除开头多余的0

最后附上代码

#include<iostream>
using namespace std;
int main()
{
	string a1, b1;
	int a[10001] = { 0 }, b[10001] = { 0 }, c[10001] = { 0 };
	cin >> a1 >> b1;//输入字符串
	int lena = a1.length();
	int lenb = b1.length();//记录字符串长度


	for (int i = 1; i <= lena; i++)a[i] = a1[lena - i] - '0';
	for (int i = 1; i <= lenb; i++)b[i] = b1[lenb - i] - '0';
	//转化为整型数组并反转数组
	
	for (int i = 1; i <= lenb; i++)
	{
		for (int j = 1; j <= lena; j++)
		{
			c[i + j - 1] += a[j] * b[i];
		}
	}//竖式乘法计算过程


	for (int i = 1; i < lena + lenb; i++)
	{
		if (c[i] > 9)
		{
			c[i + 1] += c[i] / 10;
			c[i] %= 10;
		}
	}//处理进位


	int len = lena + lenb;
	while (c[len] == 0 && len > 1)len--;//去除多余的0
	for (int i = len; i >= 1; i--)cout << c[i];//输出
	return 0;
}