title: “大数运算”
date: 2024-06-03 10:42:02
updated: 2024-06-05 07:32:22
tag: [“notion”, “Algorithm”, “数学”]
categories: “Algorithm”
mathjax: true
comments: true
description: ‘

• 大数运算

大数运算

/*
大数加,减,乘,除,比较大小
考虑翻转补0
考虑最后答案去除前导0, 以及全0情况
*/

//大数加法, 非负整数a,b
string add(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    while (a.size() < b.size()) a.push_back('0');
    while (b.size() < a.size()) b.push_back('0');
    string ans;
    int c = 0;
    for (int i=0; i<a.size(); i++) {
        int num = (a[i]-'0')+(b[i]-'0')+c;
        ans.push_back(num%10+'0');
        c = num/10;
    }
    if (c) ans.push_back(c+'0');
    reverse(ans.begin(), ans.end());
    return ans;
}

//大数比较, 可有前导0, 非负整数
int numcmp(string a, string b) {
    //注意前导0
    if (a.find_first_not_of('0') == string::npos) a = "0";
    else a = a.substr(a.find_first_not_of('0'));
    if (b.find_first_not_of('0') == string::npos) b = "0";
    else b = b.substr(b.find_first_not_of('0'));
    if (a.size() < b.size()) return -1;
    else if (a.size() > b.size()) return 1;
    else {
        if (a<b) return -1;
        else if (a>b) return 1;
        else return 0;
    }
}

//大数减法,非负整数a,b
string sub(string a, string b) {
    bool flag = false;
    if (numcmp(a, b) == 0) return "0";
    if (numcmp(a, b) == -1) {
        flag = true;
        swap(a,b);
    }
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    while (a.size()<b.size()) a.push_back('0');
    while (b.size()<a.size()) b.push_back('0');
    string ans;
    int c=0;
    for (int i=0; i<a.size(); i++) {
        int num = (a[i]-'0')-(b[i]-'0')-c;
        if (num<0) {
            num += 10;
            c = 1;
        } else c = 0;
        ans.push_back(num+'0');
    }
    reverse(ans.begin(), ans.end());
    if (flag) return "-"+ans.substr(ans.find_first_not_of('0'));
    else return ans.substr(ans.find_first_not_of('0'));
}

//大数乘法, 非负整数
string mul(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string ans="0";
    for (int i=0; i<a.size(); i++) {
        string t;
        for (int j=0; j<i; j++) t.push_back('0');
        int c = 0;
        for (int j=0; j<b.size(); j++) {
            int num = (a[i]-'0')*(b[j]-'0')+c;
            t.push_back(num%10+'0');
            c = num/10;
        }
        if (c) t.push_back(c+'0');
        reverse(t.begin(), t.end());
        ans = add(ans, t);
    }
    if (ans.find_first_not_of('0') == string::npos) return "0";//注意乘0情况会得到多个0
    return ans.substr(ans.find_first_not_of('0'));
}

//大数整除, 非负整数, 返回商和余数
pair<string, string> div(string a, string b) {
    int cp = numcmp(a, b);
    if (cp == 0) return make_pair("1", "0");
    if (cp == -1) return make_pair("0", a);
    string ans, t;
    for (int i=0; i<a.size(); i++) {
        t.push_back(a[i]);
        int c = 0;
        while (numcmp(b, t) != 1) { // b<=t
            t = sub(t, b);
            c++;
        }
        ans.push_back(c+'0');
    }
    //不会出现全零情况
    return make_pair(ans.substr(ans.find_first_not_of('0')), t);
}

//高精度除法, 非负整数, 截取到小数点后p位
string div(string a, string b, int p) {
    string ans, t;
    for (int i=0; i<a.size(); i++) {
        int c = 0;
        t.push_back(a[i]);
        while (numcmp(b, t)!=1) {
            c++;
            t = sub(t, b);
        }
        ans.push_back(c+'0');
    }
    ans.push_back('.');
    for (int i=0; i<p; i++) {
        int c = 0;
        t.push_back('0');
        while (numcmp(b, t)!=1) {
            c++;
            t = sub(t, b);
        }
        ans.push_back(c+'0');
    }
    if (ans.find_first_not_of('0') == ans.find_first_of('.'))
        return "0"+ans.substr(ans.find_first_of('.'));
    return ans.substr(ans.find_first_not_of('0'));
}