高精度运算：参与运算的数范围大大，超出了标准数据类型能表示的范围的运算。

标准数据类型可以表示的整数范围：$\text{int:}[-2^{31},2^{31})$、$\text{long long:}[-2^{63},2^{63})$. 而通过高精度算法，我们可以处理极大的数据运算，例如长度为 $10^{6}$ 的数的加减运算。

算法思路

数字储存

普通整型将数字整体二进制储存，而高精度整型将数字的每一位单独储存。即使用一个整型数组，每一位分别储存数字的每一位。

例如 $998244353$ 这个数，使用高精度储存即为 $[3,5,3,4,4,2,8,9,9]$. 为了进位方便，我们往往将数字反向储存，即个位放在数组第 $0$ 位，以此类推。当然若没有进位问题，如仅考虑除法，正向储存其实也可以，但不推荐。

运算操作

高精度算法可以看作模拟人列竖式运算，可以自己在纸上试一下竖式运算的步骤，即可理解代码的含义。

注意：下面的算法没有考虑正负性，若存在符号问题，需要修改使用方式。

高精度整型输入/输出

/* 变量 */
string a;
vector<int> A;

/* 输入 */
cin >> a; // 首先以字符串形式读入
for (int i = a.size() - 1; i >= 0; i--)
    A.push_back(a[i] - '0'); // 反向将字符串每位写入整型数组，注意减去偏移量‘0’

/* 输出 */
for (int i = A.size() - 1; i >= 0; i--)
    cout << A[i]; // 反向输出整型数组每一位

高精度整型 + 高精度整型

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (B.size() > A.size())
        return add(B, A);
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i++)
    {
        t += A[i];
        if (i < B.size())
            t += B[i];
        C.push_back(t % 10);
        t = t > 9 ? 1 : 0;
    }
    if (t)
        C.push_back(1);
    return C;
}

注意：

开头 if 的作用为保证 $A的位数\geq B的位数$，当然可以通过修改下面的循环和判断条件使其适配所有情况。
for 循环中的 if 是为了防止越界访问 $B$ 。
结尾需要判断 $t$ 是否为 $0$，若非 $0$ 则需要进位 $1$.

高精度整型 - 高精度整型

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);
        t = t < 0 ? 1 : 0;
    }
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}

注意：

改算法需要保证 $A\geq B$，即答案必须为正，因此需要用下文的调用方法。
for 循环中的 if 是为了防止越界访问 $B$ 。
$(t + 10) \% 10$ 配合下一行，简单地实现了借位操作。
结尾 while 循环功能是去除多余的前导 $0$，即 $000123$ 取出后为 $123$.

bool cmp(vector<int> &A, vector<int> &B) // 若A>=B返回true，否则返回false
{
    if (A.size() != B.size())
        return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i--)
        if (A[i] != B[i])
            return A[i] > B[i];
    return true;
}

int main()
{
    if (cmp(A, B))
        vector<int> C = sub(A, B);
    else
        vector<int> C = sub(B, A); // 这种情况输出时记得先输出一个‘-’符号
}

高精度整型 * 整型

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i++)
    {
        if (i < A.size())
            t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}

注意：

for 循环判断条件有 || t，是为了处理最后的进位。
for 循环内的 if 防止越界访问 $A$.
结尾 while 循环功能是去除多余的前导 $0$.

高精度整型 / 整型

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;
}

注意：

除法我们也是模拟的竖式除法，因此是从高位像低位计算，因此 for 循环方向与上面三种相反。
reverse 函数在头文件 algorithm 中，为了将反向的答案翻转还原。
结尾 while 循环功能是去除多余的前导 $0$.

算法 | 高精度运算