高精度加法 分为两种情况：压位，不压位

高精度压位运算

压位和不压位的高精度计算存在三点不同点（以下提到的压位都是压4位）：

（1）存储：不压位的话，vector或者数组中每个数据是0~9；压位以后，每个数据是0~9999。

（2）计算过程：不压位的话，除数和模数都是10；压位以后，除数和模数都是10000。

（3）输出：不压位的话，直接输出；压位的话，需要格式化输出，最高位直接输出即可，其他位都需要输出4位数字，不足的前面补零

高精度加法

从前往后 位数大的作为A，t存储进位
从前往后遍历整个C数组 C中存储t % 10的值 从低位开始

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

vector <int> add(vector <int> &A,vector<int> &B)
{
    if(A.size() < B.size()) add(B, A);//A的位数必须大于B的位数

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

int main()
{
    string a,b;
    vector<int> A,B;
    cin>> a >> b;

    for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

    vector<int> c = add(A, B);
    for(int i = c.size() - 1; i >= 0; i -- ) cout << c[i];
    cout<<endl;


    return 0;
}

压九位代码

#include <iostream>
#include <vector>

using namespace std;

const int base = 1000000000;

vector<int> add(vector<int> &A, vector<int> &B)
{
    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 % base);
        t /= base;
    }

    if (t) C.push_back(t);
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;

    for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
    {
        s += (a[i] - '0') * t;
        j ++, t *= 10;
        if (j == 9 || i == 0)
        {
            A.push_back(s);
            s = j = 0;
            t = 1;
        }
    }
    for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
    {
        s += (b[i] - '0') * t;
        j ++, t *= 10;
        if (j == 9 || i == 0)
        {
            B.push_back(s);
            s = j = 0;
            t = 1;
        }
    }

    auto C = add(A, B);

    cout << C.back();
    for (int i = C.size() - 2; i >= 0; i -- ) printf("%09d", C[i]);
    cout << endl;

    return 0;
}

高精度乘法拓展版本

高精度x低精度

同样从小到大遍历数组 进位存储每一位与低精度

#include <iostream>
#include <cstring>
#include <algorithm>
#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() || 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(); //去除前导零 否则会出现00000 的情况
    return 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;
}

高精度x高精度

从小到大遍历

#include <iostream>
#include <vector>
using namespace std;

vector<int> mul(vector<int> &A, vector<int> &B)
{
    vector<int> C(A.size() + B.size() + 7, 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()
{
    string a, b;
    cin >> a >> b;

    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0 ; i -- ) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0 ; i -- ) B.push_back(b[i] - '0');

    auto C = mul(A, B);

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

    return 0;
}

高精度减法

需要先存在一个比较函数 如果AB位数不等则返回A位数大于B
如果AB位数相等 判断各个字符是否相等 不等则返回A[i] > B[i]
输出模10以后的数

#include <iostream>
#include <vector>
using namespace std;

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

        return true;
}

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;//当借位为0 把其值赋为A[i]
        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()
{
    string a,b;
    cin >> a >> b;
    vector<int> A, B;

    for(int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

    vector<int> C;
    if(cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';

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

    cout << endl;
    return 0;
}

高精度除法(有些许不同)

从后往前遍历 输出r/b的答案 r = r * 10 + A[i]
最后利用reverse函数 调换顺序

#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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());//之所以需要reverse 因为遍历是从后往前遍历的 先算高位
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return 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');

    int r = 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;

}