#7. 高精度加法
高精度加法
给定两个正整数(不含前导 0),计算它们的和。
输入格式
共两行,每行包含一个整数。
输出格式
共一行,包含所求的和。
数据范围
1≤整数长度≤100000
输入样例:
12
23
输出样例:
35
已按 OJ 可直接使用的 1.in/1.out ... 25.in/25.out 生成 25 组“超大整数加法(最长 100000 位、无前导 0)”测试数据,包含多组 10^5 位压力、长进位链、不同长度、随机大数等。
下面按 1..25 逐组说明每组主要在卡哪些常见错误做法(正确:按字符从低位到高位相加处理进位;注意输出可能比最长输入多 1 位;不要用内置整型):
- 样例:基础正确性。
- 单数字无进位:卡最小规模与基本加法。
- 单数字有进位(9+8):卡进位处理。
- 长度不同且无连锁进位:卡对齐/补零逻辑。
- 长度不同且产生新位(999+1):卡最高位进位、结果长度+1。
- 超长连续进位链(很多 9 + 1):卡“进位一直传递到最前面”的实现(常见漏掉最后 carry)。
- 较大数但进位不多:卡普通大数加法的正确性。
- 1000 位随机 + 1000 位随机:综合正确性(容易暴露指针/数组越界)。
- 内部大量 0(10^k 形式):卡处理中间 0、以及大数读入输出。
- 交替数字(1010… + 9090…):卡“每位都可能进位/不进位交替”的情况。
- 一方 10000 位(1 后面 9999 个 0)+ 短数:卡长度差巨大、尾部对齐与进位影响低位。
- 两数均为 10000 位随机:卡性能与大规模正确性。
- 9999 位全 9 + 9999 位全 9:结果应为 1 后面一串 9 再 8…(总长度 10000);卡最高位进位与整串进位。
- 中等长度互补结构:卡普通加法的正确性(不应依赖数值大小顺序)。
- 大量尾随 0 vs 大量 9(…000 + …999):卡从低位开始的长进位链与对齐。
- 两段“看似随机”的常数串(π/e 相关):卡一般性正确性与多处进位。
- 极短 + 5000 位全 1:卡长度差、以及不要反向写错位置。
- 10^5 位全 9 + 1(最大压力进位链):强卡性能 + 进位传递到第 100001 位(结果长度会变成 100001)。
- 两数均为 10^5 位随机:强卡性能/内存与实现正确性(不能 O(n^2) 拼接字符串)。
- 10000 位的 510^9999 + 510^9999:只在最高位产生一次进位(结果变 1 后面 0…);卡最高位 carry。
- (1 后面 50000 个 9) + (8 后面 50000 个 0):前半大范围进位但不一定全链到最前,卡“部分长进位链”。
- 两数完全相同(重复块拼接):卡重复模式、以及可能的缓存/去重错误(不该去重)。
- 两数均 10^5 位:
1234567890重复 +9876543210重复:强卡大输入读写、每位加法正确性(规律性强,错一位很容易炸)。 - 稀疏 1(首尾有 1) + 大量 0 的大数:卡只在少数位变化、以及尾部对齐(末位加法)。
- 5000 位全 9 + 5000 位全 9:中等压力的“全链进位”,卡结果长度+1与输出。
你继续发下一题的话,我也会同样:生成 zip + 逐组解释每个数据卡什么常见错误。