洛谷 P2142 高精度减法

// ✗ 第 ① 版：64 位整数直接减 —— 题面明码标价的 20 分
//
//   · 20% 的数据：a, b 在 long long 的范围内 ⇒ **这一版全对**；
//   · 100% 的数据：a, b ≤ 10^10086 ⇒ **10087 位**，而 long long 只有 19 位 —— 差 530 倍位数。
//
// ⇒ 和[上一道 P1601](/sol/p1601/) 是同一件事的第二次：
//   **出题人写的那几行分档，就是「暴力值多少分」的答案。**
//   ⚠ 但这道题的第一档只值 20 分（P1601 那道值 40 分）——
//   **同一个偷懒的写法，在两道相邻的题上值的钱不一样。**
//
// ⚠ 用 long long（不是 unsigned）是因为这道题的答案**可以是负数**，
//   而这一版在小数据上是真的对：负号由 printf 自己打出来。
//   顶格时 `cin >>` 读失败 ⇒ 两个变量都被置成 LLONG_MAX ⇒ 打出 0（不是崩溃）。

#include <bits/stdc++.h>
using namespace std;

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

    long long a = 0, b = 0;
    cin >> a >> b;
    cout << a - b << "\n";
    return 0;
}

// P2142 高精度减法 —— ★ 正解：先判谁大，再减，最后补符号
//
// ★★ 这道题和上一道（[P1601](/sol/p1601/)）差的不是难度，是**前提**：
//   [第 44 章第 7 步](/ch/44-bignum/)那个 sub() 的注释里写着一句
//   「**调用方保证 a >= b**」—— 而这道题的题面**没有这个保证**，
//   还专门写了一行「如果 a − b < 0，请输出负号」。
//   ⇒ 照抄本章的 sub() 就是把一个**前提已经不成立的模板**搬过来（p2142NoSwap.cpp 就是它）。
//
// 所以正解比模板多了整整一层，而这一层全是「和算法无关」的活：
//   ① 比大小：**先比位数，位数相同再逐位比**（⚠ 直接用 string 的 `<` 是错的，见 p2142Lex.cpp）；
//   ② 小的减大的时候交换两个数，并且记下要打一个负号；
//   ③ 减完去前导零（1000 − 999 = 0001 → 1）；
//   ④ ⚠ `a == b` 时答案是 `0`，**不能打成 `-0`**（第 ② 步那个判断写成 `<=` 就会，见 p2142NegZero.cpp）。
//
// 复杂度 O(n)，n ≤ 10087（题面 a, b ≤ 10^10086）⇒ 一万位的减法，眨眼。

#include <bits/stdc++.h>
using namespace std;

/** −1 / 0 / 1。★ 位数不同时长的那个大，位数相同时才轮到逐位比 */
static int cmpNum(const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
    if (a == b) return 0;
    return a < b ? -1 : 1;
}

/** 高位在前的减法，调用方保证 a >= b；结果已去掉前导零 */
static string subStr(const string& a, const string& b) {
    string y = string(a.size() - b.size(), '0') + b, c(a.size(), '0');
    int borrow = 0;
    for (size_t k = a.size(); k-- > 0;) {
        int cur = (a[k] - '0') - (y[k] - '0') - borrow;
        borrow = 0;
        if (cur < 0) { cur += 10; borrow = 1; }      // ★ 借位是一条链，borrow 要带着走
        c[k] = char('0' + cur);
    }
    size_t i = 0;
    while (i + 1 < c.size() && c[i] == '0') i++;     // ★ 1000 − 999 = 0001 → 1
    return c.substr(i);
}

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

    string a, b;
    if (!(cin >> a >> b)) return 0;

    int r = cmpNum(a, b);
    if (r == 0) cout << "0\n";                        // ⚠ 这一支必须单独走，否则会打出 -0
    else if (r > 0) cout << subStr(a, b) << "\n";
    else cout << "-" << subStr(b, a) << "\n";
    return 0;
}

// P2142 解析页上所有数字的出处。./p2142Count [csv]
//
// 三件事：
//   ① 四个档位里每个 bug 的**触发条件**各满足了多少轮（拿去和对拍的抓获数逐格对）；
//   ② ★★★ **验算走一条和减法完全无关的路：把答案加回去** ——
//      `|a − b| + min(a,b)` 应该逐字节等于 `max(a,b)`。
//      加法和减法在代码上一行都不共享（一个只有进位、一个只有借位），
//      所以这不是「拿减法验减法」。
//      ⚠⚠ 而这个「0 组对不上」**配了自检才敢写**：同一段验证器拿去验那个
//      「照抄本章 sub()」的版本，当场抓出一大片（[报 0 之前先证明这段代码是活的](/sol/p1094/)）。
//   ③ 顶格一次减法要做多少次一位数减法。
#include <bits/stdc++.h>
using namespace std;

static int cmpNum(const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
    if (a == b) return 0;
    return a < b ? -1 : 1;
}

static string subStr(const string& a, const string& b) {
    string y = string(a.size() - b.size(), '0') + b, c(a.size(), '0');
    int borrow = 0;
    for (size_t k = a.size(); k-- > 0;) {
        int cur = (a[k] - '0') - (y[k] - '0') - borrow;
        borrow = 0;
        if (cur < 0) { cur += 10; borrow = 1; }
        c[k] = char('0' + cur);
    }
    size_t i = 0;
    while (i + 1 < c.size() && c[i] == '0') i++;
    return c.substr(i);
}

/** 完全无关的那条路：只有进位，没有借位 */
static string addStr(const string& x, const string& y) {
    size_t n = max(x.size(), y.size());
    string a = string(n - x.size(), '0') + x, b = string(n - y.size(), '0') + y, c(n, '0');
    int carry = 0;
    for (size_t k = n; k-- > 0;) {
        int cur = (a[k] - '0') + (b[k] - '0') + carry;
        c[k] = char('0' + cur % 10);
        carry = cur / 10;
    }
    if (carry) c = char('0' + carry) + c;
    size_t i = 0;
    while (i + 1 < c.size() && c[i] == '0') i++;
    return c.substr(i);
}

/** 「照抄本章 sub()、不判大小」那一版算出来的东西 —— 只用来给验证器做自检 */
static string noSwap(const string& a, const string& b) {
    string y = b;
    if (y.size() > a.size()) y = y.substr(y.size() - a.size());
    y = string(a.size() - y.size(), '0') + y;
    string c(a.size(), '0');
    int borrow = 0;
    for (size_t k = a.size(); k-- > 0;) {
        int cur = (a[k] - '0') - (y[k] - '0') - borrow;
        borrow = 0;
        if (cur < 0) { cur += 10; borrow = 1; }
        c[k] = char('0' + cur);
    }
    size_t i = 0;
    while (i + 1 < c.size() && c[i] == '0') i++;
    return c.substr(i);
}

static void gen(unsigned seed, int mode, string& a, string& b) {
    mt19937 rng(seed * 1000003u + 20260904u);
    int lo = mode == 3 ? 10080 : 1, hi = mode == 3 ? 10086 : 12;
    unsigned r1 = rng() % (unsigned)(hi - lo + 1);
    unsigned r2 = rng() % (unsigned)(hi - lo + 1);
    int la = lo + (int)r1, lb = lo + (int)r2;
    if (mode == 1 || mode == 2) lb = la;
    auto one = [&](int len) {
        string s;
        unsigned h = rng() % 9u;
        s += char('1' + h);
        for (int i = 1; i < len; i++) { unsigned d = rng() % 10u; s += char('0' + d); }
        return s;
    };
    a = one(la);
    if (mode == 2) {
        unsigned same = rng() % 3u;
        b = a;
        if (same != 0) {
            unsigned k = 1u + rng() % 3u;
            for (unsigned t = 0; t < k && t < a.size(); t++) { unsigned d = rng() % 10u; b[b.size() - 1 - t] = char('0' + d); }
            if (b[0] == '0') b[0] = a[0];
        }
    } else {
        b = one(lb);
    }
}

int main(int argc, char** argv) {
    bool csv = argc > 1 && string(argv[1]) == "csv";

    int tSwap[4] = {0}, tLex[4] = {0}, tTrim[4] = {0}, tEq[4] = {0}, tLl[4] = {0};
    int backBad = 0, backCases = 0, selfCaught = 0, selfCases = 0;

    for (int mode = 0; mode < 4; mode++)
        for (unsigned s = 1; s <= 300; s++) {
            string a, b;
            gen(s, mode, a, b);
            int r = cmpNum(a, b);
            if (r < 0) tSwap[mode]++;                                   // NoSwap 会错
            bool lexSaysLess = (a < b);                                 // 字典序
            if (lexSaysLess != (r < 0)) tLex[mode]++;                   // 字典序判反了
            if (r == 0) tEq[mode]++;                                    // NegZero 打 -0
            if (a.size() > 19 || b.size() > 19) tLl[mode]++;
            string big = r >= 0 ? a : b, small = r >= 0 ? b : a;
            string c = r == 0 ? string("0") : subStr(big, small);
            if (r != 0 && c.size() < big.size()) tTrim[mode]++;          // 答案位数变少 ⇒ 有前导零

            // ★★★ 反着验：把答案加回去
            backCases++;
            if (addStr(c, small) != big) backBad++;
            // ★ 自检：同一段验证器去验那个已知错的版本
            if (r < 0) {                                                // a < b 时它才错
                selfCases++;
                string w = noSwap(a, b);
                if (addStr(w, b) != a) selfCaught++;
            }
        }

    long long topLen = 10087;

    if (csv) {
        for (int m = 0; m < 4; m++) printf("trigSwap%d,%d\n", m, tSwap[m]);
        for (int m = 0; m < 4; m++) printf("trigLex%d,%d\n", m, tLex[m]);
        for (int m = 0; m < 4; m++) printf("trigTrim%d,%d\n", m, tTrim[m]);
        for (int m = 0; m < 4; m++) printf("trigEq%d,%d\n", m, tEq[m]);
        for (int m = 0; m < 4; m++) printf("trigLl%d,%d\n", m, tLl[m]);
        printf("backCases,%d\n", backCases);
        printf("backBad,%d\n", backBad);
        printf("selfCases,%d\n", selfCases);
        printf("selfCaught,%d\n", selfCaught);
        printf("topLen,%lld\n", topLen);
        return 0;
    }

    printf("=== 四个档位 × 每个 bug 的触发条件（各 300 轮）===\n");
    printf("%-40s %6s %6s %6s %6s\n", "触发条件", "档0", "档1", "档2", "档3");
    printf("%-40s %6d %6d %6d %6d\n", "a < b（照抄本章 sub 会错）", tSwap[0], tSwap[1], tSwap[2], tSwap[3]);
    printf("%-40s %6d %6d %6d %6d\n", "字典序把大小判反了", tLex[0], tLex[1], tLex[2], tLex[3]);
    printf("%-40s %6d %6d %6d %6d\n", "答案位数变少（前导零）", tTrim[0], tTrim[1], tTrim[2], tTrim[3]);
    printf("%-40s %6d %6d %6d %6d\n", "a == b（会打出 -0）", tEq[0], tEq[1], tEq[2], tEq[3]);
    printf("%-40s %6d %6d %6d %6d\n", "有数超过 19 位（64 位装不下）", tLl[0], tLl[1], tLl[2], tLl[3]);

    printf("\n=== 验算：把答案加回去（|a−b| + min == max）===\n");
    printf("%d 组里对不上的：%d 组\n", backCases, backBad);
    printf("★ 自检：同一段验证器去验「照抄本章 sub()」那一版 —— %d 组里抓出 %d 组\n", selfCases, selfCaught);
    printf("\n顶格：%lld 位的减法，%lld 次一位数减法 —— 时限 1 秒，秒表在这一章没用\n", topLen, topLen);
    return 0;
}