```cpp
string mul(string a, int b)
{
string str = "", temp_num = "";
int temp_digit = 0;
int a_len = a.length(), carry = 0;
for (int i = a_len - 1; i >= 0; i--)
{
temp_num = "";
temp_num.insert(0, a_len - 1 - i, '0'); // 这行代码有问题！！
temp_digit = (a[i] - '0') * b + carry;
carry = temp_digit / 10;
temp_digit %= 10;
temp_num = char(temp_digit + '0') + temp_num; // 这行代码也有问题！！
str = add(str, temp_num);
}
if (carry != 0)
str = to_string(carry) + str;
str.erase(0, str.find_first_not_of('0'));
if (str.empty())
str = "0";
return str;
}
```
`insert()`的时间复杂度是 $O(n)$， `string`加法也是 $O(n)$，加上外层的循环，整体就是 $O(n^2)$了，这比正常高精乘低精的复杂度 $O(n)$ 慢太多了。
究其原因是你的程序中数字是正着存储的（第一位是最高位，最后一位是最低位），这导致对齐个位需要 $O(n)$ 的时间，极大的拖慢了运算的速度，最后喜提$TLE$。
然而反着存储数字（第一位是最低位，最后一位是最高位）因为天然就对齐了个位，便不存在所谓的“对齐”一说了，只需$O(1)$便可完成。
by _xm_ @ 2023-06-09 01:47:11
@[_xm_](/user/821481) 感谢赐教！
不过还有一个疑问想请教一下
循环中使用的`temp_num.insert(0, a_len - 1 - i, '0');`是模拟乘法竖式中补0的部分
以25\*25为例（我不太会格式请海涵）：
```
25
* 25
------
125
500
------
625
```
在计算25\*20的时候，我计算了25\*2，并在后面补了一个0
这个`insert()`就是补0的意思
正序存储的话怎么省掉这个`insert()`啊？没太看懂。
by lzy20091001 @ 2023-06-09 19:37:09
emm...
## 一般我是这样列竖式的：
```
25
* 25
------
125
50 //这个0是可以省略的
------
625
```
计算`25 * 25`的过程中，问题被拆解成`5 * 25 + 20 * 25`计算；而在计算`20 * 25`时，问题又可以变成`2 * 25`
## 分析一下：
```
第一轮：
5 * 25 = 125
存入数组
3 2 1 // 下标
[0][0][125] // 填入数组
| // 从这里填入计算结果
[1][2][5] // 进位处理之后
第二轮：
2 * 25 = 50 （拆解后的20 * 25）
3 2 1 // 下标
[1][52][5] // 填入数组
| // 从这里填入计算结果
[1][6][5] // 进位处理之后
```
因为第二轮省略了一个零，要在第一轮的位置上**左移 $1$ 位**才可以填入数组。
## 然后可以推导出一般情况：
**第 $i$ 轮就从 $a[i]$ 开始填进数组，然后处理进位**
因为是高精乘低精，“个位数” $\times$ “$int$类型”，结果不超过$1 \times 10^{10}$，每次进位处理不会超过 $10$ 次，每一轮 $for$ 循环自然就是 $O(1)$。
此时整个 $for$ 循环的时间复杂度是 $O(n)$ ，问题完美解决！！
by _xm_ @ 2023-06-09 22:52:47