Table of Contents
题目
分析
本题接续P1601：A+B Problem（高精），也是高精度的常见基本算法：乘法。
我们可以将P1601的代码拷贝过来，并加入一个*运算符的重载：
class HighPrecision
{
friend istream& operator>>(istream& is, HighPrecision& hp);
friend ostream& operator<<(ostream& os, const HighPrecision& hp);
friend HighPrecision operator+(const HighPrecision& hp1,
const HighPrecision& hp2);
friend HighPrecision operator*(const HighPrecision& hp1,
const HighPrecision& hp2); // 新加'*'运算符的重载
// ...
}; 如何计算乘法呢？如果按照常规的竖式算法会比较烦。繁琐之处在于进位的处理。进位可能来自两个数字不同的位数相乘的结果，而且低位进位会影响高位的计算和进一步的进位。
通过模拟，我们会发现，a*b这样的乘法计算中，a的第i位和b的第j位相乘，只会影响两个位置，分别是i + j位（乘积的个位数）以及i + j + 1位（乘积的十位数）。
有了这个洞见后，我们就可以很容易写出乘法运算过程：
HighPrecision operator*(const HighPrecision& hp1, const HighPrecision& hp2)
{
HighPrecision hp;
hp.num.resize(hp1.num.size() + hp2.num.size(), 0); /// 一个`n`位数乘以`m`位数，乘积最多就是`n + m`位
for (int i = 0; i < hp1.num.size(); i++)
{
for (int j = 0; j < hp2.num.size(); j++)
{
hp.num[i + j] += hp1.num[i] * hp2.num[j];
hp.num[i + j + 1] += hp.num[i + j] / 10;
hp.num[i + j] %= 10;
}
}
// Remove leading zero if no final carry
while (hp.num.size() > 1 && hp.num.back() == 0)
{
hp.num.pop_back();
}
return hp;
}这个算法中，首先计算出i + j位的乘积，然后分别处理十位（也就是进位）和个位（放在本位置），并将进位放到i + j +1（也就是下一位）。
注意：加法与乘法在预留结果长度上的上限不同。加法可能需要预留max(len(a), len(b)) + 1位以保存最高位的进位；而乘法的乘积最多为n + m位（若a为n位，b为m位），因此在实现乘法时只需预留n + m位空间。
最后，去掉前导0即可。
答案
思考
高精度算法以加法和乘法为主。至于减法，其实就是加法：只要将b（加数）的每一位变成负数即可，但此时需要注意：加法是进位而减法是借位，处理上有一些不同。这个留给读者自行完成。高精度除法很烦，不会作为考试题目。
优化讨论（减少取模/除法开销）:
在上面的乘法实现中，我们在内层循环里对每次累加后的 hp.num[i+j] 都做了一次除以 10 的进位计算和一次取模操作：
hp.num[i + j] += hp1.num[i] * hp2.num[j];
hp.num[i + j + 1] += hp.num[i + j] / 10;
hp.num[i + j] %= 10;这样虽然直接保持了每一位始终在0..9的范围内，但会在每次乘法累加时执行大量的除法和取模操作（这两类操作相比整型加减更耗时）。一种更高效的做法是把所有乘积先累加到对应的位置，然后再统一做一次从低位到高位的进位传播（只对n+m个位置做一次除法/取模），从而把除/模的调用次数从\(O(n\times m)\)降到\(O(n+m)\)：
HighPrecision operator*(const HighPrecision& hp1, const HighPrecision& hp2)
{
HighPrecision hp;
int n = hp1.num.size();
int m = hp2.num.size();
hp.num.assign(n + m, 0); // 预留 n+m 位
// 1) 先累加所有乘积到对应的位上（不处理进位）
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
hp.num[i + j] += hp1.num[i] * hp2.num[j];
}
}
// 2) 统一从低位到高位传播进位（每位最多做一次除/模）
for (int i = 0; i < (int)hp.num.size() - 1; ++i)
{
if (hp.num[i] >= 10)
{
hp.num[i + 1] += hp.num[i] / 10;
hp.num[i] %= 10;
}
}
// 去掉前导零
while (hp.num.size() > 1 && hp.num.back() == 0)
{
hp.num.pop_back();
}
return hp;
}从复杂度与效果来看，乘法的乘加次数仍为\(O(n\times m)\)（无法避免），但除法与求模的次数从\(O(n\times m)\)降到了\(O(n+m)\)，在位数较大时能显著减少昂贵的除/模操作，性能更优。