大数模拟(高精度加减乘除)

由于整数位数最长可达100000，远远超出了int和long long 以及unsigned long long所能表示的范围，所以我们利用字符串string或char*类型来读入数据，利用vector容器来存储数据。输入的数据是高位在前，低位在后，而加减乘运算是从低位开始的，一般情况下我们也是从低位开始遍历vector,所以我们利用vector的低位来存储的数据的低位，vector的高位存储数据的高位。具体代码如下：

string s;
cin >> s;
vector<int> a;
for(int i=s.size()-1;i>=0;--i){
    a.push_back(s[i] - '0');
}

加

题目：高精度加法 https://www.acwing.com/problem/content/793/
没有简单的方法，笔算怎么算，代码就怎么写。
我们首先考虑两个一位数的十进制加法a + b，进位是 t,那么本位的计算结果就是(a+b+t)%10（逢10进位，所以需要模上10），进位的结果就是(a+b+t)/t。以上就是大数模拟加法的核心思路。具体代码如下：

vector<int> add(vector<int> &a,vector<int> &b){
    vector<int> v;
    int t = 0;//进位
    int len = max(a.size(),b.size());
    for(int i=0;i<len || t;++i){
        if(i < b.size()) t+=b[i];
        if(i<a.size()) t-=a[i];
        v.push_back(t%10)；
        t/=10;
    }
    return v;
}

代码要点在于循环条件，直到进位t=0才能结束。千万不要忘记进位。

减

与加法的不同之处的是减法是借位，而且还要考虑两个数的大小。
考虑两个一位数十进制减法a - b，借位是t，那么本位的计算结果是(a-b-t+10)%10，借位的结果要分情况讨论，如果a-b -t>=0,借位结果是0，反之是1。注意，由于仅考虑一位十进制数减法，所以借位不可能大于1。
此外，还有一点要注意的是如果两个数相同，那么计算结果是全0，而我们只需要一个0，所以需要去除前导零。具体代码如下：

bool cmp(vector<int> &v1,vector<int> &v2){//v1>v2返回true
    if(v1.size()!=v2.size()) return v1.size()>v2.size();
    else{
        for(int i = v1.size() - 1;i >= 0; --i){
            if(v1[i]!=v2[i]) return v1[i]>v2[i];

        }
    }
    return true;
}

vector<int> sub(vector<int> &v1,vector<int> &v2){
    if(!cmp(v1,v2)) return sub(v2,v1) 
    vector<int> v;
    int t = 0;//表示借位
    //v1是被减数，v2是减数
    for(int i = 0;i<v1.size();++i){
        t = v1[i] - t;
        if(i<v2.size()) t-=v2[i];
        v.push_back((t+10)%10);
        if(t<0) t = 1;
        else t = 0;
    }

    //需要去除前导零
    while(v.size()!=1&&!v.back()) v.pop_back();
    return v;
}

乘

通常是一个大数乘以一个较小的数，这个较小的数是int类型，而大数用字符串读入，用vector容器来计算。
代码同样是模拟手算的过程。
我们在列竖式手算的过程中是单个十进制与单个十进制相乘,如$a \times b$，本位结果是$(a \times b)%10$,进位的结果是$(a \times b)/10$。
在这里要注意，我们不把较小数拆成一位一位的形式，而是把它较小数看作是一个整体，剩下的计算过程和手算完全相同。例如，x是一个十进制个位数，而y不一定是个位数，也可能是两位数，三位数。那么$x \times y$，本位(与x所处的位数相同)的计算结果是$(x \times y)%10$，进位结果是$(x \times y)/10$。

注意事项

1. 去除前导零
2. 不要忘记进位

vector<int> mul(vector<int>& v,int b){
    int t = 0;
    vector<int> res;
    for(int i = 0;i<v.size() || t;++i){
        if(i<v.size()) t +=b*a[i];
        res.push_back(t%10);
        t/=10;
    }

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

除

除法是一个大数除以一个int类型的数字。
除法与加减乘都不太一样：
1. 除法的结果由余数和商组成。由于一个函数只能有一个返回值，要想同时得到余数和商，我们只能再定义一个全局变量，这个全局变量一般是余数。
2. 除法是从高位开始，加减乘都是从低位开始的，所以对于被除数，以字符串的形式读入，用 vector<int>来存储。其中， vector低位存储被除数的高位，高位存储被除数的低位。
3. 如果被除数的高位小于除数的话，商的高位会出现0，所以需要去除前导零。

int r;//这个是余数
vector<int> div(vector<int> &v,int b){
    vector<int> res;
    for(int i=0;i<v.size();++i){
        r = 10 * r + v[i];
        res.push_back(r/b);
        r=r%b;
    }
    reverse(res.begin(),res.end());

    //去除前导0
    while(res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}