P1601 高精度加法

题目背景

本题是高精度加法的模板题。

题目描述

给定两个非负整数 \(a,b\)，求它们的和。不用考虑负数。

输入格式

输入共两行，每行一个非负整数，分别为 \(a,b\)。

输出格式

输出一行一个非负整数，表示 \(a+b\) 的值。

输入输出样例 #1

输入 #1

1
1

输出 #1

输入输出样例 #2

输入 #2

1001
9099

输出 #2

说明/提示

对于 \(20\%\) 的测试数据，\(a,b \le 10^9\)；
对于 \(40\%\) 的测试数据，\(a,b \le 10^{18}\)；
对于 \(100\%\) 的测试数据，\(0\le a,b \le 10^{500}\)。

Tip

B站讲解

📌 题目分析

给定数据：

a, b ≤ 10^500

通过字符串模拟加法，求出两个非负整数的和。

👉 本质：

突破系统数据类型范围的限制进行运算

👉 类型：

经典 高精度加法 / 模拟竖式

🧠 解题思路

1️⃣ 为什么需要高精度运算

数据范围极大：

最大达到 500 位数字

而 C++ 中最大的基本整数类型：

long long 的极限约为 9 × 10^18（仅 19 位）

所以内置数据类型一定会溢出，必须使用字符串（string）或数组来存储数字。

2️⃣ 核心模拟逻辑（竖式加法）

就像小学数学学过的列竖式一样：

  个位对齐
  逐位同位相加
  逢十进一

用代码实现就是维护一个进位变量 carry，每一位的值为：

当前位结果 = (a的当前位 + b的当前位 + carry) % 10
新的进位 = (a的当前位 + b的当前位 + carry) / 10

3️⃣ 为什么要将字符串倒序

我们平时写数字：

字符串下标 0 是最高位（最左边）

但加法必须从最低位（个位）开始算，而且进位会向高位延伸。为了方便处理进位对齐和位数增加的情况，通常将字符串逆序：

让下标 0 变成个位，下标 1 变成十位...

这样加完之后，再把结果逆序输出即可。

4️⃣ 时间复杂度

只需遍历较长字符串的长度：

O(max(len(a), len(b)))

最大仅需循环 500 次，极快。

💻 C++代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

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

    string a, b;
    cin >> a >> b;

    // 1. 将字符串反转，使个位对齐（下标 0 为个位）
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    string res = "";
    int carry = 0; // 进位
    int len = max(a.length(), b.length());

    // 2. 模拟竖式加法
    for (int i = 0; i < len; i++) {
        // 如果对应位置有数字则取出，否则用 0 补齐
        int numA = (i < a.length()) ? (a[i] - '0') : 0;
        int numB = (i < b.length()) ? (b[i] - '0') : 0;

        int sum = numA + numB + carry;
        res += to_string(sum % 10); // 当前位的结果
        carry = sum / 10;           // 更新进位
    }

    // 3. 处理最高位可能剩下的进位
    if (carry > 0) {
        res += to_string(carry);
    }

    // 4. 将结果反转回来输出
    reverse(res.begin(), res.end());
    cout << res << "\n";

    return 0;
}

⚠️ 易错点

❌ 1. 忘记最后一位的进位

循环结束后，必须检查：

if (carry > 0)

例如 50 + 50 = 100，最后的进位 1 如果不补上，结果就会变成 00。

❌ 2. 字符与数字的转换

字符串里的 '9' 不是数字 9。必须减去 '0' 才能变成真正的数值参与运算：

a[i] - '0'

存入结果字符串时，要转回字符或者用 to_string()。

❌ 3. 两个数字长度不一致

如果不倒序，很难让它们的个位对齐。在提取每一位时，必须判断有没有越界，如果超出了某个数字的长度，就当作 0 来加：

(i < a.length()) ? (a[i] - '0') : 0

🚀 一句话总结

高精度加法 = 字符串倒序 + 逐位累加 + 逢十进一 + 结果反转

🔥 补充

高精度运算出现的场景：

超出 long long 限制的计数问题（如第100项斐波那契数列）
C/C++ 语言竞赛必考的基础模板
如果使用 Python 或 Java (BigInteger)，这道题可以直接用 a + b 秒杀，但在 C/C++ 中必须掌握手写高精度。