高精度

一、 为什么需要高精度计算？

在计算机科学的领域中，我们习惯于使用内置的数据类型来处理数字，例如 int、long long、double 等。这些类型在处理绝大多数日常计算时表现出色，它们的运算速度极快，因为现代中央处理器（CPU）有专门的硬件指令来直接支持这些运算。然而，这些数据类型并非万能，它们都有一个固有的、无法逾越的限制：表示范围。

以C++中最常用的64位整型 long long 为例，它可以表示的范围大约是从 $-9 \times 10^{18}$ 到 $9 \times 10^{18}$。这个数字看起来非常巨大，但在某些科学计算、密码学、组合数学等领域，它却显得捉襟见肘。例如，计算 $100!$（100的阶乘），其结果的位数高达158位，远远超出了 long long 的能力范围。浮点类型 double 虽然能表示更大范围的数，但它的问题在于精度有限。它只能精确表示大约15到17位十进制有效数字，在处理需要极高精度的金融计算或某些物理模拟时，微小的舍入误差可能会被放大，导致最终结果谬以千里。

当内置数据类型无法满足我们对数值范围或精度的要求时，高精度计算 (Arbitrary-Precision Arithmetic) 便应运而生。 高精度计算，又称“大数运算”，其核心思想是使用软件的方式来模拟人类进行笔算的过程，从而摆脱硬件的限制，处理理论上只受限于内存大小的任意大或任意精度的数字。

我们不再将一个巨大的数作为一个整体存储在单个变量中，而是将其“拆分”开来，用一种数据结构（通常是数组或字符串）来存储它的每一位数字。 随后，我们基于这个数据结构，用程序来模拟小学数学中学到的竖式加、减、乘、除法等运算规则，逐位进行计算，并妥善处理进位和借位。 这样，我们就能够用程序完成对这些“庞然大物”的精确计算。

二、 高精度计算的基石：存储

要实现高精度计算，首先要解决的问题是如何在计算机中表示一个大数。最直观、最常用的方法是使用数组。

2.1 数组表示法

我们可以用一个整型数组来存储一个大数的每一位。例如，对于数字 12345，我们可以用一个 int 数组 a 来表示： a[0]=5, a[1]=4, a[2]=3, a[3]=2, a[4]=1

你可能已经注意到，我们将数字的低位存储在数组的低地址（小编号）位，高位存储在数组的高地址（大编号）位。 也就是说，数组是倒序存储这个数的。这看起来似乎有些反直觉，但这么做有重要的好处：

1. 方便进位：在做加法或乘法时，运算通常从个位开始。如果个位产生进位，这个进位需要加到十位上。在倒序存储的数组中，这意味着 a[0] 的进位加到 a[1]，a[1] 的进位加到 a[2]，以此类推。这种从低索引到高索引的操作非常自然，也便于循环处理。
2. 长度易扩展：当运算结果的位数增加时（例如 99 + 1 = 100），我们只需要在数组的末尾（高位）添加新的元素，而不需要移动所有现有元素。

除了用数组存储，C++的 std::string 类型也是一个常见的选择。字符串本质上是一个字符数组，可以直接读入，且动态管理内存，非常方便。在使用时，需要注意将字符转换为对应的数字（例如 c - '0'）。同样的，为了计算方便，我们通常也会将读入的字符串逆序存储到数组中。

2.2 压位优化 (Radix Conversion)

在基础的高精度实现中，数组的每个元素只存储一位十进制数（0-9）。这非常简单，但空间和时间效率并不高。由于一个 int 类型可以存储远大于9的数（通常至少到 $2 \times 10^9$），我们可以让数组的每个元素存储多位数字，这就是“压位”技巧。

例如，我们可以选择 $10^4$（一万）或 $10^9$（十亿）作为基数（base）。如果以 $10^4$ 为基数，数组的每个元素就可以存储一个0到9999之间的四位数。数字 12345678 就可以表示为： a[0] = 5678, a[1] = 1234 运算时，我们就在这个万进制下进行加减乘除，处理相应的进位和借位。这种方式大幅减少了数组的长度，也减少了循环的次数，从而显著提高了高精度计算的效率。选择 $10^9$ 作为基数是因为它小于 int 的最大值，同时两个 $10^9$ 级别的数相加或相乘再加一个进位，其结果仍然可以在 long long 中处理，便于计算。

在本文后续的代码示例中，为了清晰地展示算法原理，我们将采用最基础的每个数组元素存储一位数字的方式。但在实际竞赛中，为了追求极致的性能，压位高精度是更常见的选择。

三、 基本四则运算

掌握了存储方法后，我们就可以着手实现核心的四则运算了。所有运算的本质都是对小学竖式计算的模拟。

3.1 高精度加法 (A + B)

高精度加法是最基础的操作。其过程完全模拟手算：

1. 将两个加数 A 和 B 逆序存入数组 a 和 b。
2. 创建一个结果数组 c，其长度可能比 a 和 b 中较长者还大1，以备最高位进位。
3. 从最低位（索引0）开始，逐位计算 c[i] = a[i] + b[i]。
4. 处理进位：设置一个进位变量 t (carry)。在计算 c[i] 时，应加上来自前一位的进位 t。计算完毕后，c[i] 的新值为 (a[i] + b[i] + t) % 10，而新的进位 t 则是 (a[i] + b[i] + t) / 10。
5. 循环直到处理完两个数的所有位。如果最后进位 t 大于0，需要将其存入结果的最高位。
6. 输出时，从高位向低位打印数组 c，并注意处理前导零（即结果的最高位不能是0，除非结果本身就是0）。

题意概括

给定两个非负整数A和B，计算A+B的和。A和B的长度可能很大。

C++ 代码示例

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

// 高精度加法
vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> c;
    int t = 0; // 进位
    for (int i = 0; i < a.size() || i < b.size(); i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s1, s2;
    cin >> s1 >> s2;

    vector<int> a, b;
    for (int i = s1.length() - 1; i >= 0; i--) a.push_back(s1[i] - '0');
    for (int i = s2.length() - 1; i >= 0; i--) b.push_back(s2[i] - '0');

    auto c = add(a, b);

    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    cout << endl;

    return 0;
}

代码解释

函数 add 接收两个逆序存储的 vector<int>，代表两个大数。循环从低位到高位模拟加法过程，变量 t 同时作为当前位的和以及下一位的进位。循环条件 i < a.size() || i < b.size() 确保两个数中较长的那个也能被完全处理。循环结束后，如果 t 仍有值，说明最高位有进位，需添加到结果中。

复杂度分析

• 时间复杂度: $O(\max(N, M))$，其中 $N$ 和 $M$ 分别是两个加数的位数。我们需要遍历两个数的所有位一次。
• 空间复杂度: $O(\max(N, M))$，用于存储结果。

3.2 高精度减法 (A - B)

减法与加法类似，只是把“进位”换成了“借位”。这里我们先假设被减数 A 大于等于减数 B，且均为非负数。

1. 比较 A 和 B 的大小，确保 A >= B。如果 A < B，则交换它们，计算 B - A，并为结果添加负号。
2. 将两个数逆序存入数组 a 和 b。
3. 从最低位开始，逐位计算 c[i] = a[i] - b[i]。
4. 处理借位：设置一个借位变量 t (borrow)。计算 c[i] 时，应是 a[i] - b[i] - t。如果结果为负，则需要向高位借1，即 c[i] 加上10，同时下一位的计算需要多减1（即 t 置为1）；否则 t 为0。
5. 循环直到处理完减数的所有位。
6. 输出时，去除前导零。一个常见的技巧是，结果数组的长度与被减数相同，最后从高位找到第一个非零位开始输出。

题意概括

给定两个非负整数A和B，计算A-B的差。A和B的长度可能很大，并保证A >= B。

C++ 代码示例

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

// 高精度减法, 确保 a >= b
vector<int> sub(vector<int> &a, vector<int> &b) {
    vector<int> c;
    int t = 0; // 借位
    for (int i = 0; i < a.size(); i++) {
        t = a[i] - t;
        if (i < b.size()) t -= b[i];
        c.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    // 去除前导零
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s1, s2;
    cin >> s1 >> s2;

    vector<int> a, b;
    for (int i = s1.length() - 1; i >= 0; i--) a.push_back(s1[i] - '0');
    for (int i = s2.length() - 1; i >= 0; i--) b.push_back(s2[i] - '0');

    auto c = sub(a, b);

    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    cout << endl;

    return 0;
}

代码解释

函数 sub 的逻辑与 add 相似。循环遍历被减数 a 的每一位。t 首先被赋值为当前位的 a[i]，然后减去上一位的借位（如果存在）。接着减去 b 对应的位。c 中存入 (t + 10) % 10 是一个巧妙的处理方式，无论 t 是正是负，这个表达式都能得到正确的当前位结果。如果 t 为负，说明发生了借位，t 更新为1，否则为0。最后，使用 while 循环去除结果中可能存在的前导零。

复杂度分析

• 时间复杂度: $O(N)$，其中 $N$ 是被减数的位数。
• 空间复杂度: $O(N)$，用于存储结果。

3.3 高精度乘法

高精度乘法比加减法复杂，分为两种情况：一个大数乘以一个普通整数（高精乘低精），以及两个大数相乘（高精乘高精）。

3.3.1 高精度乘低精度 (A * b)

这类似于用一个多位数乘以一个单位数。

1. 大数 A 逆序存入数组 a，小数为 b。
2. 逐位计算 a[i] * b，并加上来自低位的进位 t。
3. c[i] 的值为 (a[i] * b + t) % 10，新的进位 t 为 (a[i] * b + t) / 10。
4. 循环处理完 a 的所有位，若最终 t 仍大于0，需要继续处理进位，直到 t 为0。

题意概括

给定一个非负整数A和一个非负整数b，计算A*b的积。A的长度可能很大，b在 int 范围内。

C++ 代码示例

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

// 高精度乘低精度
vector<int> mul(vector<int> &a, int b) {
    vector<int> c;
    ll t = 0; // 进位, 用 long long 防止溢出
    for (int i = 0; i < a.size() || t; i++) {
        if (i < a.size()) t += (ll)a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s1;
    int b;
    cin >> s1 >> b;

    if (s1 == "0" || b == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> a;
    for (int i = s1.length() - 1; i >= 0; i--) a.push_back(s1[i] - '0');
    
    auto c = mul(a, b);

    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    cout << endl;

    return 0;
}

代码解释

mul 函数的循环条件 i < a.size() || t 非常关键，它确保即使遍历完 a 的所有位后，如果进位 t 仍然不为0，循环会继续，将所有进位都处理完毕。例如 99 * 2，处理完个位和十位后，t 还有一个值为1的百位进位需要处理。变量 t 使用 long long 是为了防止 a[i] * b 的中间结果溢出 int。

复杂度分析

• 时间复杂度: $O(N)$，其中 $N$ 是大数的位数。
• 空间复杂度: $O(N)$，结果的位数最多约为 $N + \text{log}_{10}(b)$。

3.3.2 高精度乘高精度 (A * B)

这是模拟小学竖式乘法的完整过程。 我们用 B 的每一位去乘 A，得到一系列的中间结果，然后将这些中间结果错位相加。 一个更简洁的实现思路是：

1. 大数 A 和 B 分别逆序存入数组 a 和 b。
2. 创建结果数组 c，其长度最大可达 a.size() + b.size()。
3. 使用双重循环，模拟 a 的第 i 位乘以 b 的第 j 位。其结果应该累加到 c 的第 i+j 位上，即 c[i+j] += a[i] * b[j]。
4. 双重循环结束后，c 中存储的是未处理进位的乘积结果。例如 c[0] 可能是一个很大的数。
5. 最后，统一处理 c 中的进位。从 c[0] 开始，c[i+1] += c[i] / 10，c[i] %= 10。

题意概括

给定两个非负整数A和B，计算A*B的积。A和B的长度都可能很大。

C++ 代码示例

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

// 高精度乘高精度
vector<int> mul(vector<int> &a, vector<int> &b) {
    vector<int> c(a.size() + b.size(), 0);
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            c[i + j] += a[i] * b[j];
        }
    }
    
    int t = 0; // 进位
    for (int i = 0; i < c.size(); i++) {
        t += c[i];
        c[i] = t % 10;
        t /= 10;
    }

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s1, s2;
    cin >> s1 >> s2;
    
    if (s1 == "0" || s2 == "0") {
        cout << 0 << endl;
        return 0;
    }

    vector<int> a, b;
    for (int i = s1.length() - 1; i >= 0; i--) a.push_back(s1[i] - '0');
    for (int i = s2.length() - 1; i >= 0; i--) b.push_back(s2[i] - '0');

    auto c = mul(a, b);

    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    cout << endl;

    return 0;
}

代码解释

此实现的核心在于两步：第一步通过双重循环计算各位相乘的贡献，并将结果累加到c数组的对应位置，此时不考虑进位。第二步再对c数组进行一次遍历，统一处理进位。这种“先计算，后进位”的策略让代码逻辑非常清晰。

复杂度分析

• 时间复杂度: $O(N \cdot M)$，其中 $N$ 和 $M$ 分别是两个乘数的位数。这是由双重循环决定的。
• 空间复杂度: $O(N + M)$，用于存储结果。

3.4 高精度除法

除法是四则运算中最复杂的，同样分为高精除低精和高精除高精。

3.4.1 高精度除低精度 (A / b)

这模拟了长除法的过程。

1. 大数 A 顺序存入数组 a（注意，这里为了方便从高位开始处理，采用顺序存储），除数为 b。
2. 从 A 的最高位开始处理，设置一个余数变量 r (remainder)。
3. r 先乘以10（相当于把上一位的余数移到下一位），再加上当前处理的位 a[i]。
4. c[i]（商的当前位）就是 r / b。
5. 新的余数 r 变为 r % b。
6. 循环处理完 A 的所有位，最终的 r 就是整个除法运算的余数。
7. 输出商时要注意去除前导零。

题意概括

给定一个非负整数A和一个正整数b，计算A/b的商和余数。A的长度可能很大，b在 int 范围内。

C++ 代码示例

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

// 高精度除低精度，r是余数
vector<int> div(vector<int> &a, int b, int &r) {
    vector<int> c;
    r = 0;
    // 从高位开始处理
    for (int i = a.size() - 1; i >= 0; i--) {
        r = r * 10 + a[i];
        c.push_back(r / b);
        r %= b;
    }
    // 翻转结果，使其低位在前
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s1;
    int b, r;
    cin >> s1 >> b;

    vector<int> a;
    // 顺序存储，方便从高位开始除
    for (int i = 0; i < s1.length(); i++) a.push_back(s1[i] - '0');
    
    auto c = div(a, b, r);

    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    cout << endl << r << endl;

    return 0;
}

代码解释

此代码为了方便从高位向低位进行除法，输入的大数是顺序存入数组a的。div函数模拟了长除法的每一步：将上一位的余数r乘以10，加上当前位，然后求商和新的余数。循环结束后得到的商c是顺序的（高位在前），需要reverse翻转成我们统一的低位在前格式。最后去除前导零。

复杂度分析

• 时间复杂度: $O(N)$，其中 $N$ 是被除数的位数。
• 空间复杂度: $O(N)$，用于存储商。

3.4.2 高精度除高精度 (A / B)

这是所有基本运算中最具挑战性的。 其本质思想是反复做减法。 我们可以模拟长除法的过程：

1. 对齐：将被除数A和除数B对齐。
2. 试商：估算A的前几位是B的多少倍。这一步是难点，精确估算很复杂，简单的估算可以通过A的最高位除以B的最高位来得到。
3. 做乘法和减法：将试商的结果乘以B，然后从A中减去。
4. 更新余数并重复：将A的下一位移下来补充到余数上，形成新的被除数，重复以上过程。

由于其实现非常复杂，且在大多数竞赛中不常直接考察，这里我们仅阐述其思想。在实际应用中，如果需要高效的大数除法，通常会借助已有的库，或者采用基于减法的模拟，虽然效率较低但逻辑相对简单：不断地从被除数中减去除数，直到被除数小于除数，减去的次数即为商。可以通过将被除数和除数左移（乘以10的幂）来加速这个过程。

四、 进阶乘法算法

$O(N^2)$ 的高精度乘法在处理上万甚至更长位数的数字时会变得非常缓慢。数学家们为此设计了更高效的算法。

4.1 Karatsuba 算法

Karatsuba算法是一种基于分治思想的快速乘法算法，由前苏联数学家Anatoly Karatsuba在1960年提出。 它将时间复杂度从 $O(N^2)$ 优化到了约 $O(N^{1.585})$。

假设我们要计算两个 $n$ 位数 $X$ 和 $Y$ 的乘积。我们可以将它们各自分为两半（假设 $n$ 是偶数）： $X = A \cdot 10^{n/2} + B$ $Y = C \cdot 10^{n/2} + D$ 其中 $A, B, C, D$ 都是 $n/2$ 位的数字。 那么，$X \cdot Y = (A \cdot 10^{n/2} + B) \cdot (C \cdot 10^{n/2} + D) = AC \cdot 10^n + (AD+BC) \cdot 10^{n/2} + BD$。

朴素的分治需要计算4次 $n/2$ 位的乘法（$AC, AD, BC, BD$），复杂度没有改善。Karatsuba的精妙之处在于，他发现中间项 $AD+BC$ 可以通过一次乘法间接得到： $AD+BC = (A+B)(C+D) - AC - BD$ 这样，我们只需要计算三次 $n/2$ 位的乘法：$P_1 = AC$, $P_2 = BD$, $P_3 = (A+B)(C+D)$。 最终结果为 $P_1 \cdot 10^n + (P_3 - P_1 - P_2) \cdot 10^{n/2} + P_2$。 原本的4次乘法变成了3次乘法，以及一些加减法（加减法的复杂度为 $O(N)$，远低于乘法）。根据主定理，其时间复杂度为 $T(n) = 3T(n/2) + O(n)$，解得 $T(n) = O(n^{\log_2 3}) \approx O(n^{1.585})$。

4.2 快速傅里叶变换 (FFT)

对于更大规模的数字相乘（例如数十万位以上），还可以使用基于快速傅里叶变换 (Fast Fourier Transform, FFT) 的算法，将时间复杂度进一步降低到 $O(N \log N)$。

其核心思想极为深刻：

1. 多项式表示：将一个 $n$ 位大数看作一个 $n-1$ 次多项式在 $x=10$ 处的取值。例如，123 可以看作多项式 $P(x) = 1x^2 + 2x^1 + 3x^0$ 在 $x=10$ 时的值。
2. 乘法与卷积：两个大数相乘，等价于它们对应的多项式相乘。多项式乘积的系数，恰好是原多项式系数序列的卷积。
3. 卷积定理：根据卷积定理，两个序列卷积的傅里叶变换，等于它们各自傅里叶变换的乘积。
4. 算法流程： a. 将两个大数的系数序列（即各位数字）作为输入。 b. 使用FFT在 $O(N \log N)$ 时间内计算出两个序列的离散傅里叶变换（DFT），得到点值表示。 c. 将两个点值表示的序列逐点相乘，这只需要 $O(N)$ 时间。 d. 使用逆快速傅里叶变换（IFFT），将相乘后的点值表示变回系数表示，时间也是 $O(N \log N)$。 e. 处理得到的系数序列的进位，得到最终的乘法结果。

FFT算法的实现细节复杂，涉及到复数运算，但其思想是高精度计算领域的一个重要里程碑，使得超大规模的精确计算成为可能。

五、 扩展：负数与浮点数

目前我们讨论的都是非负整数。要构建一个完整的高精度库，还需要处理负数和浮点数。

• 负数处理：通常是在高精度数结构中增加一个符号位（布尔变量）。

  • 加法：同号相加，取相同符号；异号相加，转化为大数减小数，符号同大数。
  • 减法：A - B 转化为 A + (-B)。
  • 乘除法：数值部分按正数计算，符号由“负负得正，正负得负”规则决定。

• 高精度浮点数：一种常见的实现方式是将浮点数表示为 整数部分 × 基数^指数部分 的形式，类似于科学计数法。 更简单的方法是，只用一个大整数来存储所有的数字（包括小数部分），并额外记录小数点的位置。例如，123.45 可以存为整数 12345 和小数点位置 2（表示小数点后有两位）。所有运算都按整数进行，最后根据小数点位置进行调整。

六、 题型实战演练

6.1 选择题

1. 在用数组实现高精度计算时，通常将大数的低位存储在数组的低地址位，这是为了？ A. 节省内存空间 B. 方便处理进位和借位 C. 提高CPU缓存命中率 D. 简化输出流程

2. 计算两个 N 位大数的加法，使用模拟竖式计算的方法，其时间复杂度大约是？ A. $O(1)$ B. $O(\log N)$ C. $O(N)$ D. $O(N^2)$

3. 下列哪个算法在计算超大整数（如百万位）乘法时，理论上效率最高？ A. 模拟竖式乘法 B. Karatsuba算法 C. 快速傅里叶变换 (FFT) D. 高精除低精

4. 对于高精度减法 A - B，当发现 A < B 时，正确的处理方式是？ A. 直接计算，结果取绝对值 B. 报告错误，无法计算 C. 计算 B - A，并给结果加上负号 D. 将 A 和 B 都乘以-1再相加

5. 实现 vector<int> mul(vector<int> &a, vector<int> &b) 函数（高精乘高精），结果数组 c 的长度最长可能达到多少？（设 a 和 b 的长度分别为 N 和 M） A. $N + M - 1$ B. $N + M$ C. $N \times M$ D. $\max(N, M)$

答案： 1.B, 2.C, 3.C, 4.C, 5.B

6.2 判断题

1. long long 类型可以精确表示一个30位的十进制整数。 ( 错 )
2. 高精度计算的精度和可表示范围只受限于计算机的内存大小。 ( 对 )
3. 在实现高精度乘低精度时，循环体执行的次数只由大数的位数决定，与低精度乘数的大小无关。 ( 对 )
4. Karatsuba算法通过将乘法次数从4次降为3次，实现了对传统竖式乘法的优化。 ( 对 )
5. 高精度除法可以通过重复做高精度加法来实现。 ( 错，应为减法 )

6.3 程序阅读题

阅读下面的高精度加法代码，并回答问题。

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

vector<int> add(string s1, string s2) {
    vector<int> a, b, c;
    for (char ch : s1) a.insert(a.begin(), ch - '0');
    for (char ch : s2) b.insert(b.begin(), ch - '0');
    
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); i++) {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if (t > 0) c.push_back(t);
    return c;
}

int main() {
    string n1 = "99", n2 = "1";
    vector<int> res = add(n1, n2);
    for (int i = res.size() - 1; i >= 0; i--) {
        cout << res[i];
    }
    cout << endl;
    return 0;
}

1. 问题1：a.insert(a.begin(), ch - '0'); 这行代码的作用是什么？它与 a.push_back(ch - '0'); 之后再 reverse(a.begin(), a.end()); 的效果是否相同？

   • 答：这行代码的作用是将字符转换的数字插入到 vector 的头部。其效果与 push_back 后再 reverse 是一样的，都是为了实现将数字逆序存储到数组中。但 insert 到头部的效率（$O(N)$）通常低于 push_back（均摊 $O(1)$），所以后者加 reverse 的组合是更优的实践。

2. 问题2：如果将 main 函数中的 n1 改为 "123"，n2 改为 "877"，程序的输出是什么？

   • 答：程序将输出 1000。计算 123 + 877 = 1000。

3. 问题3：如果 add 函数的 if (t > 0) c.push_back(t); 语句被误写为 if (t > 0) c.push_back(t % 10);，当输入为 "9", "9" 时，add 函数返回的 vector 内容是什么（从索引0开始）？

   • 答：t 的最终值为18，c 的第一位是 18 % 10 = 8，t 变为 1。if 条件满足，执行 c.push_back(1 % 10)，即 c.push_back(1)。所以返回的 vector 是 {8, 1}。

6.4 程序补全题

补全下面的高精度乘低精度代码中的空白部分。

题意：计算一个大整数乘以一个 int 范围内的数。

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

vector<int> mul(vector<int> &a, int b) {
    vector<int> c;
    ll t = 0; // 进位
    
    // (1) 循环条件
    for (int i = 0; ____________________; i++) {
        if (i < a.size()) t += (ll)a[i] * b;
        
        // (2) 计算当前位
        c.push_back(____________);
        
        // (3) 更新进位
        t = ____________;
    }
    
    // (4) 去除前导零
    while (_____________________________) {
        c.pop_back();
    }
    
    return c;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s1;
    int b;
    cin >> s1 >> b;
    
    vector<int> a;
    for (int i = s1.length() - 1; i >= 0; i--) a.push_back(s1[i] - '0');

    if (s1 == "0" || b == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    auto c = mul(a, b);

    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    cout << endl;

    return 0;
}

答案：

1. i < a.size() || t
2. t % 10
3. t / 10
4. c.size() > 1 && c.back() == 0