[数据结构与算法]【算法】C++高精度计算（加、减、乘、除）

洛谷相应练习（代码经检验通过）：
P1601 A+B Problem（高精）
P2142 高精度减法
P1303 A*B Problem
P1480 A/B Problem

源代码：

#include <bits/stdc++.h>

using namespace std;

const int len = 10096; //最大位数

int a[len], b[len], c[len];

int compare(string s1, string s2){
    if(s1.length() > s2.length()) return 0;
    if(s1.length() < s2.length()) return 1;
    for(int i = 0; i < s1.length(); i++){
        if(s1[i] > s2[i]) return 0;
        if(s1[i] < s2[i]) return 1;
    }
    return 2;
}

int compare(int a[], int b[]){
    if(a[0] > b[0]) return 1;
    if(a[0] < b[0]) return -1;
    for(int i = a[0]; i > 0; i--){
        if(a[i] > b[i]) return 1;
        if(a[i] < b[i]) return -1;
    }
    return 0;
}

void sub(int a[], int b[]){
    int flag = compare(a,b);
    if(flag == 0){
        a[0] = 0;
        return;
    }
    if(flag == 1){
        for(int i = 1; i <= a[0]; i++){
            if(a[i] < b[i]){
                a[i + 1]--;
                a[i] += 10;
            }
            a[i] -= b[i];
        }
        while((a[0] > 0) && (a[a[0]] == 0)) a[0]--;
        return;
    }
}

class BigInteger{
public:
    BigInteger(){ s = "0"; }
    BigInteger(string str){ s = str; }
    string toString()const;
private:
    string s;
};

string BigInteger::toString()const{
    return s;
}

BigInteger operator+(const BigInteger &b1, const BigInteger &b2){
    string s1 = b1.toString();
    string s2 = b2.toString();
    string s3;
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    a[0] = s1.length();
    for(int i = 1; i <= a[0]; i++) a[i] = s1[a[0] - i] - '0';
    b[0] = s2.length();
    for(int i = 1; i <= b[0]; i++) b[i] = s2[b[0] - i] - '0';
    int maxlen = (a[0] > b[0] ? a[0] : b[0]);
    for(int i = 1; i <= maxlen; i++){
        a[i] += b[i];
        a[i + 1] += (a[i] / 10);
        a[i] %= 10;
    }
    maxlen++;
    while((a[maxlen] == 0) && (maxlen > 1)) maxlen--;
    for(int i = 0; i < maxlen; i++) s3 += char(a[maxlen - i] + '0');
    return BigInteger(s3);
}

BigInteger operator-(const BigInteger &b){
    string s = "-";
    s += b.toString();
    return BigInteger(s);
}

BigInteger operator-(const BigInteger &b1, const BigInteger &b2){
    string s1 = b1.toString();
    string s2 = b2.toString();
    string s3;
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    a[0] = s1.length();
    for(int i = 1; i <= a[0]; i++) a[i] = s1[a[0] - i] - '0';
    b[0] = s2.length();
    for(int i = 1; i <= b[0]; i++) b[i] = s2[b[0] - i] - '0';
    if((compare(s1, s2) == 0) || (compare(s1, s2) == 2)){
        for(int i = 1; i <= a[0]; i++){
            a[i] -= b[i];
            if(a[i] < 0){
                a[i + 1]--;
                a[i] += 10;
            }
        }
        a[0]++;
        while((a[a[0]] == 0) && (a[0] > 1)) a[0]--;
        for(int i = 0; i < a[0]; i++) s3 += char(a[a[0] - i] + '0');
        return BigInteger(s3);
    }else{
        s3 = "-";
        for(int i = 1; i <= b[0]; i++){
            b[i] -= a[i];
            if(b[i] < 0){
                b[i + 1]--;
                b[i] += 10;
            }
        }
        b[0]++;
        while((b[b[0]] == 0) && (b[0] > 1)) b[0]--;
        for(int i = 0; i < b[0]; i++) s3 += char(b[b[0] - i] + '0');
        return BigInteger(s3);
    }
    return BigInteger(0);
}

BigInteger operator*(BigInteger &b1, BigInteger &b2){
    string s1 = b1.toString();
    string s2 = b2.toString();
    string s3;
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    a[0] = s1.length();
    for(int i = 1; i <= a[0]; i++) a[i] = s1[a[0] - i] - '0';
    b[0] = s2.length();
    for(int i = 1; i <= b[0]; i++) b[i] = s2[b[0] - i] - '0';
    memset(c, 0, sizeof(c));
    for(int i = 1; i <= a[0]; i++){
        for(int j = 1; j <= b[0]; j++){
            c[i + j - 1] += a[i] * b[j];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] %= 10;
        }
    }
    int maxlen = a[0] + b[0] + 1;
    while((c[maxlen] == 0) && (maxlen > 1)) maxlen--;
    for(int i = 0; i < maxlen; i++) s3 += char(c[maxlen - i] + '0');
    return s3;
}

BigInteger operator/(BigInteger &b1, int &b){
    int lena, lenc, x = 0;
    memset(a, 0, sizeof(a));
    memset(c, 0, sizeof(c));
    string s1 = b1.toString();
    string s2;
    lena = s1.length();
    for(int i = 0; i <= lena - 1;i++) a[i + 1] = s1[i] - '0';
    for(int i = 1; i <= lena; i++){
        c[i] = (x * 10 + a[i]) / b;
        x = (x * 10 + a[i]) % b;
    }
    lenc = 1;
    while ((c[lenc] == 0) && (lenc < lena)) lenc++;
    for(int i = lenc; i <= lena; i++) s2 += char(c[i] + '0');
    return BigInteger(s2);
}

BigInteger operator/(BigInteger &b1, BigInteger &b2){
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    string s1 = b1.toString();
    string s2 = b2.toString();
    a[0] = s1.length();
    b[0] = s2.length();
    for(int i = 1; i <= a[0]; i++) a[i] = s1[a[0] - i] - '0';
    for(int i = 1; i <= b[0]; i++) b[i] = s2[b[0] - i] - '0';
    int temp[len];
    c[0] = a[0] - b[0] + 1;
    for(int i = c[0]; i > 0; i--){
        memset(temp, 0, sizeof(temp));
        for(int j = 1; j <= b[0]; j++) temp[j + i - 1] = b[j];
        temp[0] = b[0] + i - 1;
        while(compare(a, temp) >= 0){
            c[i]++;
            sub(a, temp);
        }
    }
    while((c[0] > 0) && (c[c[0]] == 0)) c[0]--;
    string s3;
    if(c[0] == 0) return BigInteger("0");
    else for(int i = c[0]; i > 0; i--) s3 += char(c[i] + '0');
    return BigInteger(s3);
}

BigInteger operator%(BigInteger &b1, BigInteger &b2){
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    string s1 = b1.toString();
    string s2 = b2.toString();
    a[0] = s1.length();
    b[0] = s2.length();
    for(int i = 1; i <= a[0]; i++) a[i] = s1[a[0] - i] - '0';
    for(int i = 1; i <= b[0]; i++) b[i] = s2[b[0] - i] - '0';
    int temp[len];
    c[0] = a[0] - b[0] + 1;
    for(int i = c[0]; i > 0; i--){
        memset(temp, 0, sizeof(temp));
        for(int j = 1; j <= b[0]; j++) temp[j + i - 1] = b[j];
        temp[0] = b[0] + i - 1;
        while(compare(a, temp) >= 0){
            c[i]++;
            sub(a, temp);
        }
    }
    while((c[0] > 0) && (c[c[0]] == 0)) c[0]--;
    string s3;
    if(a[0] == 0) return BigInteger("0");
    else for(int i = a[0]; i > 0; i--) s3 += char(a[i] + '0');
    return BigInteger(s3);
}

int main(){
    string s1, s2;
    while(cin >> s1 >> s2){
        BigInteger b1(s1);
        BigInteger b2(s2);
        BigInteger b3;
        // 求加法
        b3 = (b1 + b2);
        cout << "加法：" << b3.toString() << endl;
        // 求减法
        b3 = (b1 - b2);
        cout << "减法：" << b3.toString() << endl;
        // 求乘法
        b3 = (b1 * b2);
        cout << "乘法：" << b3.toString() << endl;
        // 求除法
        b3 = (b1 / b2);
        cout << "除法（高精 / 高精）：" << b3.toString() << endl;
        // 求商
        b3 = (b1 % b2);
        cout << "商：" << b3.toString() << endl;
    }
    return 0;
}