高精度

主要是用来对超出int范围外的数字进行算数运算的一种算法

高精度 & 4

• 加法
• 减法
• 乘法
• 除法

高精度加法

假如现在给两个高精度的数字A，B

首先我们需要将A的每一位存储到数组或者是集合当中，B也是同样的道理(当然这里需要反向存储，因为我们需要先去计算个位，然后判断下一位是否需要进位)

在进行加法运算的时候我们需要考虑这一位上是否有数，我们只需要加上A，B上这一位有数的值即可

第i位保留的结果为和取模操作，除以10判断下一位是否需要进位

循环结束我们需要判断t是否还有值，如果有值只需要再添加一个1代表进位操作。ex：90 + 10 当i = 2的是否t 等于1，我们需要在00的前面加上一即可

#include <bits/stdc++.h>
using namespace std;
vector<int> add(vector<int> &A,vector<int> &B) {
    vector<int> C;
    int i = 0,t = 0;
    while(i < A.size() || i < B.size()) {
        if(i < A.size()) t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
        i++;
    }
    
    if(t) C.push_back(1);
    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 res = add(A,B);
    for(int i = res.size() - 1;i >= 0;i--) cout << res[i];
    cout << endl;
    return 0;
}

高精度减法

和高精度加法一样，我们反向存储字符串

如果发现对位差值为负数的话，那么下一位需要先减1，再进行A[i] - B[i]的操作

最后别忘了，需要去前导0，当然如果A - B结果就是0的话，那么没有必要去0了

#include <bits/stdc++.h>
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;
        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');
    
    if(cmp(A,B)) {
        auto ans = sub(A,B);
        for(int i = ans.size() - 1;i >= 0;i--) cout << ans[i];
    }else {
        auto ans = sub(B,A);
        cout << "-";
        for(int i = ans.size() - 1;i >= 0;i--) cout << ans[i];
    }
    cout << endl;
    return 0;
}

高精度乘法

以下代码主要适用于A为高精度数字，B为int范围内的数字

如果两个都是高精度数字，A的长度为N，B的长度为M，时间复杂度为O(N * M)很容易超时

所以很少出现两个数都是高精度的情况

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

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

        t /= 10;
    }

    if(t) v.push_back(t);

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

    return v;
}


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];
    return 0;
}

高精度除法

思路

举个例子：200 / 3 -> (2 / 3 == 0) -> (2 * 10 / 3 == 6) -> (2 * 10 / 3 == 6) ———> 066 -> 66

我们是从分母进行出发，每一次向C中添加的位为每一位/ 3的值，下一位的初始值设置为上一次保存下来的值 * 10 + 本次的值接着进行同样的取模和除法运算

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

vector<int> mul(vector<int> &A,int b,int &t) {
    vector<int> C;
    t = 0;
    for(int i = A.size() - 1;i >= 0;i--) {
        t = t * 10 + A[i];
        C.push_back(t / b);
        t %= b;
    }
    
    reverse(C.begin(),C.end());
    
    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;
    auto c = mul(A,b,r);
    
    for(int i = c.size() - 1;i >= 0;i--) cout << c[i];
    cout << endl;
    cout << r << endl;
    return 0;
}