题目分析
题目要求计算两个非负整数的乘积,但每个数最多有 2000 位。
* 普通 int、long long 最多存十几位,存不下这么大的数
* 必须用字符串存数字,模拟我们手写竖式乘法来计算
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、核心思路
我们平时笔算乘法是这样的:
程序模拟步骤:
1. 把两个大数用字符串读入
2. 为了方便从个位开始算,逆序处理
3. 用数组存结果:a第i位 × b第j位 结果放在 i+j 位置
4. 统一处理进位
5. 去掉前导 0,逆序输出答案
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、重要规律(必记)
* 两个数长度分别为 n、m,乘积最长为 n + m 位
* a 的第 i 位(从0开始,个位是0) × b 的第 j 位
→ 结果落在 i + j 这一位
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、完整代码 + 逐行详解
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、每一步详细解释
1. 输入与存储
* 数字太大,用 string 存储
* 例如输入 123,字符串是 "123"
2. 逆序取数字
* 字符串下标:0='1', 1='2', 2='3'
* 我们要从个位开始乘,个位是最后一位:s[len-1-i]
* '0' 是字符,减 '0' 变成整数:'5'-'0' = 5
3. 乘法核心
* 第 i 位 × 第 j 位 → 放在 i+j 位
* 先把所有乘积加完,最后统一进位
4. 进位处理
* 比如某一位是 25
* 进位:25/10 = 2 给下一位
* 本位:25%10 = 5
5. 去前导0
* 结果可能是 000535,要变成 535
* 从最高位往前扫,遇到 0 就跳过
* 至少保留一位 0,防止结果是 0 时什么都不输出
6. 输出
* 数组里是逆序存的(个位在前)
* 从后往前输出就是正常顺序
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、样例演示
输入:
* len1=1, len2=1
* i=0, j=0: ans[0] = 1×2 = 2
* 进位后还是 2
* 输出 2
输入:
计算后得到 5535,正确输出。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、边界情况测试
1. 0 × 0 → 输出 0
2. 0 × 123456 → 输出 0
3. 999...9(2000个9)× 999...9 → 正确输出超大结果
这些情况代码都能正确处理。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、时间复杂度
* 两层循环:O(n × m)
* 2000 × 2000 = 4,000,000 次运算
* C++ 完全无压力,不会超时