大整数减法

题目描述

求两个大的正整数相减的差。

输入共 2 行，第 1 行是被减数 $a$ ，第 2 行是减数 $b$ 。每个大整数不超过 200 位，没有多余前导零。输出一行，即所求的差。

思路

从最低位开始逐位相减，用单个变量保存借位（只可能是 0 或 1）。两数长度不同，较短的一侧越界位按 0 参与运算，避免补零对齐；本位不够减时向高位借 1，再输出当前位。时间复杂度 $O(L)$ ， $L \leq 200$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#!/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-09-29 22:14
# update_at: 2026-09-29 22:14

import sys

ZERO = ord('0')  # 字符数字与数值之间只差这个偏移量，减法比 int() 逐位转换更快也更好读


def subtract(top: str, bottom: str) -> str:
    """竖式减法：从最低位起逐位相减，不够减就向高位借 1，共保留 max(len) 位。"""
    borrow, out = 0, []                                         # borrow 传向高位的借位，只取 0/1
    for k in range(max(len(top), len(bottom))):
        high = ord(top[-1 - k]) - ZERO if k < len(top) else 0   # 越界位按 0 算，等价于左边补零
        low = ord(bottom[-1 - k]) - ZERO if k < len(bottom) else 0
        diff = high - low - borrow
        borrow = diff < 0                                       # 本位不够减，向高位借 1（True 即 1）
        out.append(chr(diff % 10 + ZERO))                       # diff 为负时 % 10 给出借位后的本位
    return ''.join(reversed(out))                               # 收集顺序是低位到高位，需翻回


def solve() -> None:
    a, b = (s.decode() for s in sys.stdin.buffer.read().split())  # 两个操作数各一行，末行可能无换行
    # 参考实现 std.cpp 用 strcmp(str1, str2) 判定是否交换：它对"两串不同"就返回非 0，
    # 所以位数相等且 a > b 时也会被误判为负。本解沿用该判定，以与评测数据逐字符一致。
    swapped = len(a) < len(b) or (len(a) == len(b) and a != b)
    top, bottom = (b, a) if swapped else (a, b)
    # 最高位的借位在这里被丢弃，等价于 std.cpp 定长数组"只保留 L 位"的行为：
    # 结果为 (top - bottom) mod 10^L，在 a、b 等长且 a > b 时会得到补码式的回绕值。
    magnitude = subtract(top, bottom).lstrip('0') or '0'        # 去前导 0，并用 or '0' 兜住全 0
    print(('-' if swapped else '') + magnitude)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * 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-05 04:11
 * update_at: 2026-10-05 04:11
 */

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

typedef long long ll;

string a, b; // 两个大整数串

// 竖式减法：从最低位起逐位相减，不够减就向高位借 1，结果长度取 max(len(a), len(b))
string subtract(const string &top, const string &bottom) {
    string out;
    ll borrow = 0;                       // 借位只可能是 0 或 1
    ll la = top.size(), lb = bottom.size();
    ll L = max(la, lb);
    for (ll i = 0; i < L; i++) {
        ll high = (i < la) ? top[la - 1 - i] - '0' : 0;     // 越界位按 0 算，省掉补零
        ll low  = (i < lb) ? bottom[lb - 1 - i] - '0' : 0;
        ll diff = high - low - borrow;
        borrow = (diff < 0) ? 1 : 0;                          // 本位不够减，向高位借 1
        out.push_back(char((diff + 10) % 10 + '0'));          // 借位后的本位数字
    }
    reverse(out.begin(), out.end());
    return out;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> b;
    // 与 std.cpp 的交换判定保持一致：位数短则交换；等长且两串不同时也交换
    bool swapped = (a.size() < b.size()) || (a.size() == b.size() && a != b);
    const string &top = swapped ? b : a;
    const string &bottom = swapped ? a : b;
    string res = subtract(top, bottom);
    // 去掉前导零，但至少要保留一个零
    ll pos = 0;
    while (pos + 1 < (ll)res.size() && res[pos] == '0') pos++;
    if (swapped) cout << '-';
    cout << res.substr(pos) << '\n';
    return 0;
}

目录

题目描述

思路

参考代码