【例1.2】高精度加法

GitHub跳转原题关系图返回列表

把两个不超过 100 位的非负整数按个位对齐倒序存进整型数组,逐位相加并传递进位,最后处理最高位进位并倒序输出。

OJ: roj

题目 ID: 2127

难度:普及-

标签:高精度模拟python

创建: 2026-10-08 07:45

更新: 2026-10-08 07:45

形式化题目

给定两个非负整数的十进制表示 AA、BB,每个数的位数不超过 100100。 输入为两行,每行一个数;输出一行,即 A+BA + B 的十进制表示(无前导零,结果为 00 时输出单个 0)。

即求

C=A+B,0⩽A,B<10100,C = A + B, \qquad 0 \leqslant A, B < 10^{100},

并输出 CC 的十进制串。样例输入为 A=22222222222222222222A = 22222222222222222222、B=33333333333333333333B = 33333333333333333333,输出 5555555555555555555555555555555555555555。

正解

思路

朴素做法及瓶颈。 直接 cin >> a >> b 用整型相加,C++ 里最大的定长类型 unsigned long long 上界约 1.8×10191.8 \times 10^{19},只能容纳 20 位,而本题最大 100 位,必然溢出。 换更大的类型也走不通——这是硬件字长的限制,不是换个声明能绕过的。所以必须换一种数据表示: 不用"一个数"来存,而用"一串数位"来存,把一次大数加法降解成一串小整数加法。

关键观察:十进制加的每一位之间是解耦的,只通过进位耦合。 第 ii 位的输出只依赖 AA 的第 ii 位、BB 的第 ii 位和来自第 i−1i-1 位的进位。于是竖式加法 (低位对齐、逐位相加、满十进一)可以逐位模拟:

Si=ai+bi+carryi−1,ci=Si mod 10,carryi=⌊Si/10⌋.S_i = a_i + b_i + \text{carry}_{i-1}, \qquad c_i = S_i \bmod 10, \qquad \text{carry}_i = \lfloor S_i / 10 \rfloor .

因为每一位的和至多是 9+9+1=199 + 9 + 1 = 19,进位永远是 00 或 11,可以用一个整型变量携带。

对齐靠倒序。 人类书写时高位在左,而竖式要从最低位开始。把字符串倒序展开成整型数组后, 下标 00 就是个位(10010^0)、下标 ii 对应 10i10^i,两个位数不同的加数自动按个位对齐; 较短的那个数高位位置保持 00(C++ 里靠全局数组默认零初始化,Python 里靠 zip_longest(fillvalue='0')), 不需要任何长度判断。

边界之一:最高位进位。 循环跑完长度较长的那个数之后,进位可能仍是 11(例如 99+199 + 1、10100−110^{100} - 1 加自身), 此时必须再补一位,否则结果会少一位。

边界之二:前导零。 加法本身不会凭空制造前导零(除 0+00 + 0 外),但如果黑盒数据里出现带前导零的输入 (本题数据生成脚本会造这种点),输出就要做一次规范化:从最高位往下丢掉前导零,并至少保留一位, 使 0+00 + 0 输出单个 0 而不是空行。

综合起来,整道题的算法就是 O(L)O(L) 的一次竖式模拟:读入 O(L)O(L)、倒序展开 O(L)O(L)、逐位相加 O(L)O(L)、 输出 O(L)O(L),其中 L⩽101L \leqslant 101。

代码

Python 版(同样是竖式模拟,不借用 int 的大数能力,与 C++ 逐位对应):

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 07:45
# update_at: 2026-10-08 07:45

import sys
from itertools import zip_longest


def add_vertically(a: str, b: str) -> str:
    """竖式加法:低位对齐逐位相加、进位往上传递,返回无前导零的十进制结果。"""
    carry = 0
    low_to_high: list[str] = []  # 结果从低位往高位收集,输出前整体翻转
    # 倒序遍历两个加数,短的那边补 '0',等价于 C++ 里全局数组初值全为 0
    for x, y in zip_longest(reversed(a), reversed(b), fillvalue='0'):
        carry, digit = divmod(int(x) + int(y) + carry, 10)  # 本位留 digit,进位传高位
        low_to_high.append(str(digit))
    if carry:
        low_to_high.append('1')  # 最高位进位,如 99 + 1 = 100
    return ''.join(reversed(low_to_high)).lstrip('0') or '0'  # 去前导零,0 + 0 输出 0


def solve() -> None:
    data = iter(sys.stdin.read().split())
    a, b = next(data), next(data)
    print(add_vertically(a, b))


if __name__ == "__main__":
    solve()

C++ 版:

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 07:45
 * update_at: 2026-10-08 07:45
 */
// 一本通 2127《【例1.2】高精度加法》:两个不超过 100 位的非负整数求和。
// 做法:字符串读入 -> 倒序展开成数字(下标 0 是个位,天然按个位对齐)
//       -> 逐位相加并传递进位 -> 处理最高位进位 -> 倒序输出。
// 位数上限 100,加上最高位进位共 101 位,数组开到 105 留余量。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXLEN = 105;  // 位数上限 100 + 最高位进位 1 + 余量
int a[MAXLEN];           // a[i] = 第一个加数第 i 位(权重 10^i),全局默认 0 使不等长自动对齐
int b[MAXLEN];           // b[i] = 第二个加数第 i 位
int c[MAXLEN];           // c[i] = 和的第 i 位

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    if (!(cin >> s1 >> s2)) return 0;  // 按 token 读入,可容忍行尾空白

    int len1 = s1.length();
    int len2 = s2.length();
    // 倒序展开:最低位落在下标 0,两个加数即使位数不同也自动按个位对齐
    for (int i = 0; i < len1; i++) a[i] = s1[len1 - 1 - i] - '0';
    for (int i = 0; i < len2; i++) b[i] = s2[len2 - 1 - i] - '0';

    int len = max(len1, len2);
    int carry = 0;  // 进位,每一位上只可能是 0 或 1
    for (int i = 0; i < len; i++) {
        int sum = a[i] + b[i] + carry;  // 短的那边高位是 0,不需要额外判断
        c[i] = sum % 10;                // 本位保留个位
        carry = sum / 10;               // 进位交给下一位
    }
    if (carry > 0) c[len++] = carry;    // 最高位进位,如 99 + 1 = 100

    // 去掉前导零(输入带前导零时会出现),结果至少保留一位,故 0 + 0 输出单个 0
    while (len > 1 && c[len - 1] == 0) len--;
    for (int i = len - 1; i >= 0; i--) cout << c[i];
    cout << '\n';
    return 0;
}

复杂度

  • 时间:O(L)O(L),L⩽101L \leqslant 101 是结果的位数(100 位加数 + 最高位进位)。每轮循环是常数次加减与取模, 实测整个程序在 11 ms 量级(限时 1000 ms)。
  • 空间:O(L)O(L),三个长度约 105105 的全局整型数组加一个输入字符串,占用在 KB 级(限时 64 MB)。
  • Python 侧:main.py 的算法与 C++ 完全同阶(O(L)O(L)),但逐位做 int() / divmod 的常数比 C++ 大, 好在 L⩽101L \leqslant 101 时完全无风险;若把 add_vertically 换成 print(int(a) + int(b)) 也是同一阶, 这里保留竖式写法是为了和题解正文的推导一一对应。

总结

  • 大数的表示先于大数的运算:不能用一个整型装下,就退回"每位一个元素"的数组/字符串表示, 再用人类竖式的规则在数组上重定义加法。
  • 倒序展开是通用技巧:让下标 00 代表个位,既省掉了右对齐的长度讨论,又让"进位往上传递"变成下标自增, 高精度加法、减法、乘法的低位对齐都靠它。
  • 两个必须检查的边界:循环结束后仍为 11 的进位(补最高位),以及输入或结果里的前导零(规范化输出)。
  • 语言差异:Python 的 int 本身是高精度实现,int(a) + int(b) 可直接过题; 但 C++ 必须手写竖式,本题的价值就在于把这套流程写清楚。

补充说明

  • 本题素材源里带有数据生成脚本(data.py),data/ 的 10 个点是自造的;题面属于"一本通"例题, 网上存在多个重建版本,出题意图与原书可能有细微差异(例如是否允许输入前导零、是否保证 A,B>0A, B > 0)。 本解按最保守的语义实现:允许前导零、允许全零、允许位数悬殊(如 100 位加 1 位), 这几种情况在 data/ 中分别对应「前导零/零值」「99⋯9+199\cdots9 + 1」「悬殊长度」三类点。
  • 素材源 std.cpp 与本解语义一致(倒序存位、逐位进位、补最高位、去前导零),差别只在实现细节: 它把缓冲开到 100000100000 位并把输出拼成一个字符串一次性写出。两版对 10 个真实点均给出相同结果。
  • 本解对 10 个真实数据点全部通过(check_sample.py),main.py 与 main.cpp 逐点一致。