高精度

A和B的位数约为\(10^6\)，即len(A)和len(B)的结果为\(10^6\)

a的数值小于等于\(10^9\)，即a<=10^9

1. 大整数是如何表示的

用int肯定是不行的，一般把大整数存储在数组里，并且要存储的数的最低位要放在数组索引为0的位置，即倒序存储。

大整数存储要倒序的原因：

在对大整数做运算时，很可能出现进位的情况。当正序存储且需要进位时，就需要把数组中的所有元素后移一位，腾出最高位的空间。但是这会大大提高程序运行的时间复杂度，因此选择使用倒序存储。

大整数的运算是一个模拟人工加法/减法/乘法/除法的过程。

通常以字符串的形式读入大整数，然后通过for循环遍历字符串中的每个元素，存储到vector<int>中。注意，在存储的时候，要将字符串中的字符元素转化为整型元素，即a[i] - '\0'.

2. 两个比较大的整数相加A+B

2.1 实现原理

串行进位加法器：从最低位开始计算，每一位的运算都是\(A_i+B_i+t\)，其中\(A_i\)是被加数的第\(i\)位、\(B_i\)是加数的第\(i\)位、\(t\)是上一位的进位。最初状态时，\(t\)被赋初值\(0\)，相当于向最低位的进位为\(0\)。

2.2 代码模板

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)	// 接收结果时, 可以使用auto类型
{
    if (A.size() < B.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 /= 10;
    }
    if (t) C.push_back(t);
    return C;
}
/*
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;
}
*/

3. 两个比较大的整数相减A-B

3.1 实现原理

(1) 两步实现：

1. 判断A和B的大小。如果A>=B，直接算A-B；如果A<B，计算B-A后加上负号。

   // 判断是否有 A >= B
   bool cmp(vector<int> A, vector<int> B)
   {
       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];		// A > B
       return true;	// A = B
   }

2. 计算A-B

(2) 对于每一位的计算：需要计算\(A_i-B_i-t\)，其中\(A_i\)是被减数的第\(i\)位、\(B_i\)是减数的第\(i\)位、\(t\)是上一位借位。最初状态时，\(t\)被赋初值\(0\)，相当于向最低位的借位为\(0\)。如果其结果>=0，则直接为该位的计算结果；如果其结果<0，则说明该位不够减，应该向上一位借位，从而在结果上+10。\(t\)根据借位与否，决定其之后的值是1还是0。

3.2 代码模板

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 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();		// 去掉前导0
    return C;
}

4. 一个大整数乘一个小整数A*a

4.1 实现原理

对于每一位的计算：分别计算当前位于乘数的乘积。计算 \((A_i*b+t)\%10\) 作为当前位的计算结果，\((A_i+b+t)/10\) 作为当前位的进位，并赋值给 \(t\)。其中，\(A\) 是乘数（大整数）、\(b\) 是小整数、\(t\) 是上一位的进位。

4.2 代码模板

// C = A * b, A >= 0, b >= 0
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;
}

5. 一个大整数除以一个小整数A/b

5.1 实现原理

模拟人工除法的过程：定义被除数为 \(A\)（大整数）、除数为 \(b\)（小整数）、余数 \(r\)（小整数），初始时 \(r\) 的值定义的 \(0\)。计算每一位的时候，\((r*10+A_i)/b\) 作为当前位的商，\((r*10+A_i)\%b\) 作为当前位的余数。

计算结束后，由于计算结果不满足倒序存储，因此需要调用reverse(C.begin(), C.end())反转存储结果，使结果满足倒序存储。

5.2 代码模板

// A / b = C ... r, A >= 0, b > 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;
}