当数字位数较大时，用int甚至用double存放是肯定会爆掉的，所以我们用数组来存放，每一个数组元素存放一位数字。

• 例如一个9位整数123456789，我们将它存入数组，一般把个位数存在a[0]，即a[0]到a[8]是987654321。这样做的原因是我们进行比如加法乘法运算的时候可能会在最高位上有进位，而在数组a[0]端插入数据很麻烦，要把后面所有数字往后移动；而在数组末尾插入数据就很简单，所以我们把最高位“1”放在最高位a[8]。

• 可以用vector来存放大整数，因为vector自带一个size函数来表示数组长度，不用额外变量来存

高精度运算，实际上就是模拟人工在纸上运算的过程

高精度加法

每一次运算实际上是三个数相加：Ai+Bi+t，其中t是上一位的进位

例题：原题连接

//a.push_back(x)相当于把x插入到vector a的尾部
#include <bits/stdc++.h>
#include <vector>
using namespace std;

//C = A + B
vector<int> add(vector<int> &A,vector<int> &B)  
//函数返回类型是vector<int>，&的目的是不用copy一份数据，效率更高
{
    vector<int> C;
    int t = 0;  //进位,初始化为0
    for(int i = 0;i<A.size() || i<B.size();i++)
    {
        //Ai + Bi + t
        if(i<A.size()) t+=A[i];  
        if(i<B.size()) t+=B[i];
        C.push_back(t%10);
        t /= 10;
    }
    if(t)  //最后还有进位，就单独进一位(加法进位只能是1)
    {
        C.push_back(1);
    }
    return C;
}

int main()
{
    string a,b;     //两个加数因为太大，所以用字符串读进来
    cin>>a>>b;    //比如a = “123456”
    vector<int> A,B;
    for(int i = a.size() - 1;i>=0;i--)   //倒着遍历，将大整数放入vector
    {
        A.push_back(a[i]-'0');  //A = [6,5,4,3,2,1]
    }
    for(int i = b.size() - 1;i>=0;i--)
    {
        B.push_back(b[i]-'0');  //把字符型转成int型 ‘6’——6
    }
    vector<int> C = add(A,B);    //也可以写成auto C = add(A,B)
    for(int i = C.size() - 1;i>=0;i--)
    {
        cout<<C[i];      //倒序输出即可得到正确数字
    }
    return 0;
}

高精度减法

每一次运算实际上是三个数相减：Ai-Bi-t，其中t是上一位的借位
当Ai-Bi-t大于0，则结果就是Ai-Bi-t。否则需要借位，就是Ai-Bi-t+10

A-B我们要保证A>B，如果要算小-大，就先大-小，再加上负号。
1. A>=B 直接算A-B
2. A<B 先算B-A,再输出他的相反数

例题：原题链接

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

//判断A>=B是否成立
bool cmp(vector<int> &A, vector<int> &B)
{
    //首先判断位数，位数大的肯定大
    if(A.size()!=B.size())
    {
        return A.size() > B.size();   //A比B长就return true，否则return false
    }
    else  //AB位数一致
    {
        for(int i = A.size() - 1;i>=0;i--)  //从高位开始比
        {
            if(A[i] != B[i])
            {
                return A[i]>B[i];   //同理，若A[i]>B[i]，代表A大于B，return true
            }
        }
        return true;     //跳出循环了还没执行return则执行return true，因为AB相等，满足A>=B
    }
}

//C = 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++)     //因为A>B,所以只需要判断i<A.size()
    {
        // Ai - Bi - t
        t = A[i] - t;
        if(i<B.size())  //B的位数还没完
        {
            t -= B[i];
        }
        //当t = Ai - Bi - t>=0,直接存入，否则+10.我们可以直接统一表示为 (t+10)%10
        //t>=0时，(t+10)%10 == t，t<0时，(t+10)%10 == t+10
        C.push_back((t+10)%10);
        if(t<0)
        {
            t = 1;   //t<0，即向下一位借位了，下一位运算时要直接先-t即-1
        }
        else
        {
            t = 0;   //没有借位
        }
    }
    //比如123-120,得到的是003，C中存放的是300，所以我们要去除“前导0”
    while(C.size()>1 && C.back() == 0)  //我们要保证C至少有一位（0也是一位），C.back()返回C中最后一位
    {
        C.pop_back();   //删除C中最后一位元素
    }
    return C;    //记得return
}

int main()
{
    string a,b;  
    cin>>a>>b;  //例如a = “123456”
    vector<int> A,B;
    for(int i = a.size() - 1;i>=0;i--)
    {
        A.push_back(a[i] - '0');   //A = [6,5,4,3,2,1]
    }
    for(int i = b.size() - 1;i>=0;i--)
    {
        B.push_back(b[i] - '0');  //一定不要忘了char到int的转换
    }
    if(cmp(A,B))  //A>=B成立
    {
        auto C = sub(A,B);
        for(int i = C.size() - 1;i>=0;i--)
        {
            cout<<C[i];
        }
    }
    else  //B大于A，即我们要求的A-B是负数。就先计算B-A，然后加个负号就行
    {
        auto C = sub(B,A);
        cout<<'-';
        for(int i = C.size() - 1;i>=0;i--)
        {
            cout<<C[i];
        }
    }

    cout<<endl;
    return 0;
}

高精度乘法

一般只讨论一个大整数×一个小整数（int范围）

例题：原题连接

//c[i] = [A[i] * b + t] % 10, t = t/10
#include <bits/stdc++.h>
#include <vector>
using namespace std;
vector<int> mul(vector<int> A,int b)
{
    vector<int> C;
    int t = 0;
    for(int i = 0;i < A.size();i++)  
    {
        t += A[i]*b;
        C.push_back(t%10);
        t = t/10;
    }
   if(t)   //要进新一位
   {
       C.push_back(t);   
       //可以发现和加法的模板是很像的，加法的t只能是0/1，而乘法都有可能
   }
   while(C.size()>1 && C.back()==0)   //去除前导0，比如b = 0，c会等于0000……
   {
       C.pop_back();
   }
    return C;  //别忘了返回C啊
}
int main()
{
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    for(int i = a.size() - 1;i>=0;i--)
    {
        A.push_back(a[i] - '0');
    }
    auto C = mul(A,b);
    for(int i = C.size()-1;i>=0;i--)
    {
        cout<<C[i];
    }
    cout<<endl;
    return 0;
}

高精度除法

一个高精度的大整数除一个低精度int的数

• 除法和加减乘不同，除法是从高位开始运算的，所以单单做除法的时候，把大整数正序存入数组可能会简单一些。但一般题目都是加减乘除混合运算，为了统一，我们还是用逆序存储，即a[0]存放最低位。

例题：原题链接

#include <bits/stdc++.h>
#include <vector>
using namespace std;
//C = A / b
vector<int> div(vector<int> &A,int b,int &r)  //引用传递余数r，这里的r变了main里的也会跟着变
{
    vector<int> C;
    r = 0;  //初始化余数
    for(int i = A.size() - 1;i>=0;i--)  //除法是先算高位的
    {
        r = r*10 + A[i];   //比如下一位是2，此时余数是1，则1*10 + 2 = 12
        C.push_back(r/b);  //商是整除
        r = r%b;     //余数是取模
    }
    //此时C中是正序存储答案数字的，为了统一，我们将其逆序
    reverse(C.begin(),C.end());

    while(C.size()>1 && C.back()==0)  //去除前置0
    {
        C.pop_back();
    }
    return C;
}

int main()
{
    string a;
    vector<int> A;
    vector<int> C;
    int b;
    int r;  //余数
    cin>>a>>b;
    for(int i = a.size()-1;i>=0;i--)
    {
        A.push_back(a[i]-'0');
    }
    C = div(A,b,r);
    for(int i = C.size() - 1;i>=0;i--)
    {
        cout<<C[i];
    }
    cout<<endl<<r<<endl;
    return 0;
}