加法

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

const int N = 1e5 + 10;

string A, B;
vector<int> a, b;

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 > 0) c.push_back(t);

    while(c.size() > 1 && c.back() == 0) c.pop_back();

    return c;
}

int main()
{
    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');
    }

    auto c = add(a, b);


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

    return 0;
}

减法

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

string A, B;
vector<int> a, b;

bool cmp(vector<int> &a, vector<int> &b)//a >= b
{
    int la = a.size();
    int lb = b.size();

    if(la != lb) return la > lb;

    for(int i = la - 1; i >= 0; i--)//从高位往低位比,类似于人比较数的过程
    {
        if(a[i] != b[i]) return a[i] > b[i];
    }

    return 1;
}

vector<int> sub(vector<int> &a, vector<int> &b)
{
    vector<int> c;
    if(!cmp(a, b))//不要使用字符串直接比较（如果小于，会无限递归），用函数传的参数比较
    {
        cout << '-';
        return sub(b, a);
    }
    int t = 0;//记录记录中间结果并保存借位
    for(int i = 0; i < a.size(); i++) //注意a >= b即 la >= lb,所以i < la即可
    {
        t = a[i] - t;
        if(i < b.size()) t -= b[i];//如la > lb
        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()
{
    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');

    auto c = sub(a, b);
    for(int i = c.size() - 1; i >= 0; i--)
    {
        cout << c[i];
    }

    return 0;
}

大*小

vector<int> mul(vector<int> &a, int b)
{
    vector<int> c;
    int t = 0;//记录中间结果并保存 错位(举例1111*12 便清楚) 的值
    for(int i = 0; i < a.size(); i++)
    {
        t = a[i] * b + t;
        c.push_back(t % 10);
        t /= 10;//错位,下一次循环的加需要
    }

    while(t)//错位后的数不止一位,每一位都要加入到c中
    {
        c.push_back(t % 10);
        t /= 10;
    }

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

对比上下两端代码,下面更加简短,但上面更好理解

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

    return C;
}

大 / 小

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

int b;
string A;
vector<int> a;

pair<vector<int>, int> div(vector<int> &a, int b)
{
    vector<int> c;


    int r = 0;//r保存中间结果 并 记录余数, 最后 保存的是最终的余数
    for(int i = a.size() - 1; i >= 0; i--)//从高位开始
    {
        r = r * 10 + a[i];//中间结果
        c.push_back(r / b);
        r %= b;//记录余数
    }
    //此时的c是正向的
    reverse(c.begin(), c.end());
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return {c, r};
}

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

    auto c = div(a, b);
    for(int i = c.first.size() - 1; i >= 0; i--)
    {
        cout << c.first[i];
    }
    cout << endl << c.second;

    return 0;
}

高精度 * 高精度
高精度乘高精度
基本思想先将 A[i]B[j] 放在 C[i+j] 上，然后过一遍 C 处理进位即可
m位n位 = n + m位(后面除法的位数是逆过程)

// O(nm)
// C = A * B, A >= 0, B >= 0
vector<int> mul(vector<int> &a, vector<int> &b)
{
    vector<int> c(a.size() + b.size());//一定要初始化 c 的大小(最大位数),后续用到 下标直接访问c
    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++)//注意c的大小, 最后的进位 一定会被 分割成一位一位的, 无需(2)的代码
    {
        t += c[i];
        c[i] = t % 10;//注意是覆盖
        t /= 10;//进位
    }

    //(2)    
    // cout << t << endl;
    // while(t)//剩余的进位,拆分成 一位一位的
    // {
    //     c.push_back(t % 10);
    //     t /= 10;
    // }
    while(c.size() > 1 && c.back() == 0) c.pop_back();

    return c;
}

O(n - m * (n))
高精度 / 高精度(此时无法使用逐位试商法 而是使用 减法模拟除法 参考他人代码+自己思考)(需要用到高精度减法)

例子:
78945/345
78945-34500 * 2 = 9945 (不断减 34500 直到不够减为止)
9945-3450 * 2 = 3045
3045-345 * 8= 285
因此，商就是 228, 余数就是 285

pair<vector<int>, vector<int>> div(vector<int> a, vector<int> b)
{
    vector<int> c, r;
    int la = a.size(), lb = b.size();
    int d = la - lb;//d是补零的个数
    c.resize(d + 1, 0);//商的最大位数是d（而下标是从0开始，所以开d + 1）,最高位可能是0,后续删去前导零即可

    for(int i = d; i >= 0; i--)//枚举补0的个数+同时i为但前计算的c[i] (两层含义)
    {
        vector<int> t_b(i, 0);//被减数,保存补0后的b
        for(int x : b)
        {
            t_b.push_back(x);
        }

        //如果第一位商0,那么不运行,默认最高位为0       
        //例如12345 / 153 第一次 12345 - 15300 a < t_b,不运行  
        while(cmp(a, t_b))//直至 a < t_b
        {
            c[i]++;//减一次 加一次(i是补几个0，实际是c的i+ 1位，下标从0开始)
            a = sub(a, t_b);
        }
    }
    r = a;//最后剩余的是余数(vector可以直接赋值)
    while(c.size() > 1 && c.back() == 0) c.pop_back();

    return {c, a};
}