高精度：乘法

算法理解

第 i 位与第 j 位相乘，只会贡献给结果的第 i + j 位；累加全部乘积后统一处理进位即可。

• 复杂度：朴素竖式 O(nm)。
• 注意：结果数组至少要有 n + m + 1 位；超长数据再考虑 FFT 或 NTT。

模板代码

#include <bits/stdc++.h>
using namespace std;

const int maxn=40500; 
int a[maxn], b[maxn], c[maxn];

int main()
{
	string s1,s2;
	cin>>s1>>s2;
	reverse(s1.begin(),s1.end());
	reverse(s2.begin(),s2.end());
	int n=s1.size();
	int m=s2.size();
	for(int i=0;i<n;i++) a[i]=s1[i]-'0';
	for(int i=0;i<m;i++) b[i]=s2[i]-'0';
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			c[i+j]+=a[i]*b[j];
		}
	}
	int len=n+m;
	for(int i=0;i<len;i++)
	{
		if(c[i]>=10)
		{
			c[i+1]+=c[i]/10;
			c[i]%=10;
		}
	}
	while(len>1 && c[len-1]==0) len--;
	for(int i=len-1;i>=0;i--)
	{
		cout<<c[i];
	}

	return 0;
}