高精度运算模板

高进度加法模板

vector<int> add(vector<vector<int>>& metric)
{
    int carry = 0; // 记录上一位的进位
    vector<int> res; // 用于记录计算结果

    // 模拟加法
    for(int i = 0; i < metric[0].size() || i < metric[1].size() || carry; i ++)
    {    
        // 因为vector数值不会初试化为0，故判读可加再加
        if(i < metric[0].size()) carry += metric[0][i];
        if(i < metric[1].size()) carry += metric[1][i];
        res.push_back(carry % 10); // 当前位的值
        carry /= 10; // 计算下一位的进位
    }
    return res;
}

高精度减法

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector<int> sub(vector<int> a, vector<int> b);
// 让绝对值大的减绝对值小的，好写代码
bool cmp(vector<int> a, vector<int> b);

int main(void)
{
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> a, b;

    for(int i = s1.size() - 1; i >= 0; i --) a.push_back(s1[i] - '0');
    for(int i = s2.size() - 1; i >= 0; i --) b.push_back(s2[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 --) printf("%d", c[i]);

    return 0;
}

vector<int> sub(vector<int> a, vector<int> b)
{
    int borrow = 0; // 上一位对该位的借位
    vector<int> c;
    // a的长度大于等于b
    for(int i = 0; i < a.size(); i ++)
    {
        // a一定有的减
        borrow = a[i] - borrow;
        if(i < b.size()) borrow -= b[i];
        // 无需借位 + 10 不影响结果，需借位 + 10 模拟借位之后的运算
        c.push_back( (borrow + 10) % 10 );
        // 不借位结果为负，则需借位
        if(borrow < 0) borrow = 1;
        else borrow = 0;
    }

    // 处理前导零（高位相同减来的）
    while(c.size() > 1 && !c.back()) c.pop_back();

    return c;
}


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> mul(vector<int> a, int b)
{
    // a是零则结果为零，没毛病
    // b是零才会出现前导零，故特判
    if(b == 0) return {0};
    int carry = 0;
    vector<int> c;
    // 乘法的进位carry可能会很大，故对最高位的进位可能不止进行一次
    for(int i = 0; i < a.size() || carry; i ++)
    {
        if(i < a.size()) carry += a[i] * b;
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

高精度除法模板

// 通过引用带回最后的余数
vector<int> div(vector<int> a, int b, int& remain)
{
    vector<int> c;
    remain = 0;
    // 除法是从高位开始算，但是为了在混合高精度运算过程中和其他运算统一，
    // 被除数也做了逆置
    for(int i = a.size() - 1; i >= 0; i --)
    {
        // 当下的被除数是上一次的余数乘以10再加上当下位的值
        remain = remain * 10 + a[i];
        c.push_back(remain / b);
        remain %= b;
    }
    // 为了统一最后的输出，这里也做逆置
    reverse(c.begin(), c.end());
    // 处理前导零（刚开始除不动商零来的）
    while(c.size() > 1 && !c.back()) c.pop_back();
    return c;
}