大數減法 題解

簡潔題意

給兩個最多 \(10^6\) 位、沒有前導零的非負整數 \(x\) 與 \(y\)，輸出 \(x - y\)；答案可能是負數。第 \(1\) 子題組（\(3\) 分）保證 \(x > y\)，第 \(2\) 子題組（\(2\) 分）沒有額外限制。

解法

15.8 的大數減法有一個先決條件：被減數不能比較小。第 \(1\) 子題組保證 \(x > y\)，直接就是 15.8 的程式；第 \(2\) 子題組要自己補上「比大小＋補負號」那一層：

  1. 先比大小：沒有前導零時，位數多的比較大；位數一樣多，從最高位找第一個不同的位——正是字串的字典序比較（8.9），也就是大數比大小整題在做的事。若 \(x < y\)，交換兩數、記下「答案是負的」。
  2. 算差：交換後被減數一定不小，照 15.8 逐位相減，再統一借位——哪一格是負的就 +10、向上一格 -1。
  3. 收尾：去前導零（保底至少留一位），最後若第 1 步記了負號就先印 -。\(x = y\) 時差是 \(0\)，而比較用的是嚴格小於、負號旗標不會被設起來，自然不會印出 -0。

常犯錯誤

  • 沒先比大小（WA）：\(x < y\) 時最高位借不到東西，會留下一格負數，印出來是亂的；範例 5 會抓到這個錯
  • 印出 -0（WA）：判負要用嚴格小於；範例 4（\(0 - 0\)）會抓到這個錯
  • 字典序比較沒先比位數（WA）："9" > "10" 在字典序下成立，但 \(9 < 10\)——跟大數比大小同一個陷阱
  • 前導零沒刪乾淨或刪過頭（WA）：\(1000 - 999\) 是 0001，要刪成 1；但別把 0 刪成空字串，去零迴圈要保底留一位

參考程式碼

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

// 把字串形式的非負整數，轉成「個位住在索引 0」的數字陣列（15.7）
vector<int> toDigits(const string& s) {
    int len = s.size();
    vector<int> d(len);
    for (int i = 0; i < len; i++) d[i] = s[len - 1 - i] - '0';
    return d;
}

// 沒有前導零時：位數多的比較大；位數一樣多就比字典序（8.9）
bool lessThan(const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
}

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

    string x, y;
    cin >> x >> y;

    bool neg = lessThan(x, y);     // x < y：答案是負的，改算 y - x
    if (neg) swap(x, y);

    vector<int> A = toDigits(x);   // 此後保證被減數不小
    vector<int> B = toDigits(y);
    int n = A.size();

    vector<int> C(n, 0);           // 差不會比被減數更長
    for (int i = 0; i < n; i++) C[i] += A[i];
    for (int i = 0; i < (int)B.size(); i++) C[i] -= B[i];

    for (int i = 0; i + 1 < n; i++) {     // 統一借位：把每一格拉回 0~9
        if (C[i] < 0) {
            C[i] += 10;
            C[i + 1] -= 1;
        }
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();   // 去前導零，至少留一位

    if (neg) cout << '-';          // x == y 時 neg 是 false，不會印 -0
    for (int i = (int)C.size() - 1; i >= 0; i--) cout << C[i];
    cout << '\n';
    return 0;
}

複雜度：\(O(|x| + |y|)\)。