Day 30 · 高精度运算 + 30 天总结

题意：给定两个非负整数 a、b，求 a + b。题目明确说了不用考虑负数。

思路

就是第 3 节手推的那套：读成字符串 → 倒序存 → 逐位相加并传进位 → 去前导零 → 倒着输出拼回字符串。

关键的一句是循环条件 i < len || carry，它保证了「最高位进位」不会丢。

1
1

2

1001
9099

10100

完整代码

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

typedef vector<int> Big;            // 倒序存放：big[0] 是个位

Big toBig(const string &s){
    Big a;
    for(int i = (int)s.size() - 1; i >= 0; i--) a.push_back(s[i] - '0');
    return a;
}

string toStr(Big a){
    while(a.size() > 1 && a.back() == 0) a.pop_back();   // ★ 去前导零
    string s;
    for(int i = (int)a.size() - 1; i >= 0; i--) s += char('0' + a[i]);
    return s;
}

Big addBig(const Big &a, const Big &b){
    Big c;
    int len = (int)max(a.size(), b.size());
    int carry = 0;                              // 进位
    for(int i = 0; i < len || carry; i++){       // ★ carry 也当循环条件
        int t = carry;
        if(i < (int)a.size()) t += a[i];
        if(i < (int)b.size()) t += b[i];
        c.push_back(t % 10);
        carry = t / 10;
    }
    return c;
}

int main(){
    string sa, sb;
    cin >> sa >> sb;
    cout << toStr(addBig(toBig(sa), toBig(sb))) << endl;
    return 0;
}

易错点

• 循环条件漏了 || carry：999 + 1 会输出 000。
• 用 cin >> long long 读：501 位的数读进来直接失败（这是 40 分和 100 分的分界线）。
• 忘了去前导零：1 + 1 会输出 02。
• 字符串转数组时忘了减 '0'：存进去的是 ASCII 码 48 ~ 57，算出来全是错的。
• a、b 有前导零：题目说「非负整数」，理论上输入可能写成 00123。 我的模板对这种情况天然兼容（去前导零在 toStr 里做了，输入有前导零也不影响求和）。

题意：给定两个正整数 a、b，求 a − b。如果结果是负数，要输出负号。

思路

减法模板只能算「大减小」，所以分两步：

1. 先用 cmpBig 比较 a 和 b 的大小。
2. 如果 a ≥ b，直接输出 subBig(a, b)；否则输出一个负号，再输出 subBig(b, a)。

2
1

1

完整代码

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

typedef vector<int> Big;

Big toBig(const string &s){
    Big a;
    for(int i = (int)s.size() - 1; i >= 0; i--) a.push_back(s[i] - '0');
    return a;
}

string toStr(Big a){
    while(a.size() > 1 && a.back() == 0) a.pop_back();
    string s;
    for(int i = (int)a.size() - 1; i >= 0; i--) s += char('0' + a[i]);
    return s;
}

// 比较大小（先去掉前导零再比）：a > b 返回 1，a < b 返回 -1，相等返回 0
int cmpBig(Big a, Big b){
    while(a.size() > 1 && a.back() == 0) a.pop_back();   // ★ 必须先规范化
    while(b.size() > 1 && b.back() == 0) b.pop_back();
    if(a.size() != b.size()) return a.size() < b.size() ? -1 : 1;   // 位数多的更大
    for(int i = (int)a.size() - 1; i >= 0; i--)                      // 从高位往下逐位比
        if(a[i] != b[i]) return a[i] < b[i] ? -1 : 1;
    return 0;
}

// 高精度减法（要求已经保证 a >= b，结果非负）
Big subBig(const Big &a, const Big &b){
    Big c;
    int borrow = 0;                             // 借位
    for(int i = 0; i < (int)a.size(); i++){
        int t = a[i] - borrow - (i < (int)b.size() ? b[i] : 0);
        if(t < 0){ t += 10; borrow = 1; }       // ★ 不够减，向前借一位
        else borrow = 0;
        c.push_back(t);
    }
    return c;                                   // 前导零交给 toStr 处理
}

int main(){
    string sa, sb;
    cin >> sa >> sb;

    Big a = toBig(sa), b = toBig(sb);

    if(cmpBig(a, b) >= 0){
        cout << toStr(subBig(a, b)) << endl;
    }else{
        cout << '-' << toStr(subBig(b, a)) << endl;   // ★ 负号 + 绝对值的差
    }
    return 0;
}

易错点

• 直接用字符串比大小："100" < "99"，位数不同的比较一定错。必须比长度。
• 比大小前忘了去前导零："099" 长度是 3，会被误判成比 "100" 还大吗？ 其实 "099" vs "100" 长度相同，逐位比第一位 0 < 1 就对了； 但 "099" vs "9" 长度 3 > 1 就会误判成 099 > 9。所以 先规范化。
• 忘了 a < b 的情况：只写 subBig 不判符号，会输出一堆乱码（借位借穿了）。
• 负数结果是 0 的时候：1 − 1 = 0，cmpBig 返回 0，走的是 >= 0 分支， 输出 0，不会输出 -0。如果你写成 if(cmpBig(a,b) > 0)， 那么 1 − 1 就会走 else 分支输出 -0 —— 这是个很隐蔽的坑。
• 借位忘了减：t = a[i] - b[i] 少了 - borrow，结果会偏大。

题意：给出两个非负整数，求它们的乘积。

思路

套第 4 节的乘法模板。三个关键点再强调一次：

1. 结果数组开 a.size() + b.size() 位 —— m 位数乘 n 位数最多 m + n 位。
2. c[i + j] += a[i] * b[j]，先全部堆着。
3. 最后从低位到高位统一处理进位。

1 
2

2

完整代码

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

typedef vector<int> Big;

Big toBig(const string &s){
    Big a;
    for(int i = (int)s.size() - 1; i >= 0; i--) a.push_back(s[i] - '0');
    return a;
}

string toStr(Big a){
    while(a.size() > 1 && a.back() == 0) a.pop_back();
    string s;
    for(int i = (int)a.size() - 1; i >= 0; i--) s += char('0' + a[i]);
    return s;
}

// 高精度乘法
Big mulBig(const Big &a, const Big &b){
    if((a.size() == 1 && a[0] == 0) || (b.size() == 1 && b[0] == 0))
        return Big(1, 0);                       // ★ 任何数乘 0 都是 0

    Big c(a.size() + b.size(), 0);              // 结果最多这么长
    for(int i = 0; i < (int)a.size(); i++)
        for(int j = 0; j < (int)b.size(); j++)
            c[i + j] += a[i] * b[j];            // ★ 先统统堆到 i+j 位上

    int carry = 0;                              // ★ 最后统一处理进位
    for(int i = 0; i < (int)c.size(); i++){
        int t = c[i] + carry;
        c[i]  = t % 10;
        carry = t / 10;
    }

    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

int main(){
    string sa, sb;
    cin >> sa >> sb;
    cout << toStr(mulBig(toBig(sa), toBig(sb))) << endl;
    return 0;
}

易错点

• 边乘边进位：c[i+j] 会被加多次，先堆后进位是硬性要求。
• 结果数组开小了：开成 a.size() + b.size() - 1 在最高位有进位时会越界。 直接开 a.size() + b.size()，多一位不用白不用。
• 最多只有 4000 位，别开 10⁶ 的数组：按输入长度动态开就好，用 vector 最省心。
• 乘数是 0 时输出了空串：如果不用 toStr 里的 > 1 保护，数组会被砍空。
• 这题没有负数和前导零的坑（题面说非负整数），但下一题 P1009 会用到乘法模板的变体。

题意：用高精度算出 S = 1! + 2! + 3! + … + n!，n ≤ 50。

思路

不要想着「先算 50! 再回头算 49!」—— 那样每次都要重算一遍乘法，很浪费。递推着来：

先手算一遍小数据（n = 3）

1! + 2! + 3! = 1 + 2 + 6 = 9 ✓ 正好是样例输出。

3

9

完整代码

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

typedef vector<int> Big;

Big toBig(const string &s){
    Big a;
    for(int i = (int)s.size() - 1; i >= 0; i--) a.push_back(s[i] - '0');
    return a;
}

string toStr(Big a){
    while(a.size() > 1 && a.back() == 0) a.pop_back();
    string s;
    for(int i = (int)a.size() - 1; i >= 0; i--) s += char('0' + a[i]);
    return s;
}

// 高精度加法
Big addBig(const Big &a, const Big &b){
    Big c;
    int len = (int)max(a.size(), b.size());
    int carry = 0;
    for(int i = 0; i < len || carry; i++){
        int t = carry;
        if(i < (int)a.size()) t += a[i];
        if(i < (int)b.size()) t += b[i];
        c.push_back(t % 10);
        carry = t / 10;
    }
    return c;
}

// 高精度 × 低精度（k 是一个普通的 int）
Big mulInt(const Big &a, int k){
    if(k == 0) return Big(1, 0);
    Big c;
    long long carry = 0;
    for(int i = 0; i < (int)a.size() || carry; i++){
        long long t = carry;
        if(i < (int)a.size()) t += (long long)a[i] * k;   // ★ 一位对上整个 k
        c.push_back((int)(t % 10));
        carry = t / 10;
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

int main(){
    int n;
    cin >> n;

    Big fact = toBig("1");      // 当前的阶乘 i!
    Big sum  = toBig("0");      // 累加和

    for(int i = 1; i <= n; i++){
        fact = mulInt(fact, i);     // i! = (i-1)! * i
        sum  = addBig(sum, fact);   // 累加
    }

    cout << toStr(sum) << endl;
    return 0;
}

易错点

• 把 fact 初始化成 0：那样整个循环乘出来一直是 0，答案也是 0。 必须初始成 1（0! = 1 是数学定义）。
• 每次重新从头算阶乘：for i: for j = 1..i: fact *= j， 虽然 n ≤ 50 也能过，但完全没必要 —— 用递推 i! = (i−1)! × i 一遍就够。
• 乘低精度时进位用 int：k 一大就溢出了。统一用 long long。
• 忘了 sum 也要用高精度：50 个 65 位的数相加，肯定也是高精度。
• 以为 n ≤ 20 就够了：题目提示专门说了书上代码只支持 n ≤ 20， 必须真的用高精度才能过 n = 50。