高精度模版

高精度加法

vector<int> add(vector<int> &A, vector<int> &B) {  //654321 654321
    vector<int> C;  
    int temp = 0;  
    for (int i = 0; i < A.size() || i < B.size(); ++i) {  
        if (i < A.size())temp += A[i];  
        if (i < B.size())temp += B[i];  
        C.push_back(temp % 10);  
        //这里除10导致进位的1会被保留!做下一位运算时的计算是:temp = A+B+是否有进位的1
        temp /= 10;//temp/=10的结果只能是0或1
    }  
    if (temp)C.push_back(1);  
    return C;  
}  
  
void high_precision() {  
    string a, b;  
    vector<int> A, B;  
    cin >> a >> b;// 123456 123456  
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');//654321  
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');//654321  
    vector<int> c = add(A, B);  
    for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);  
}

高精度减法

bool compare(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--)//此时a, b位数相同
        if (a[i] != b[i])return a[i] > b[i];  
    return true;//此时a == b  
}  
  
/**  
 * // C = A - B, 满足A >= B, A >= 0, B >= 0
 * @param A * @param B * @return */
vector<int> sub(vector<int> &a, vector<int> &b) {  
    vector<int> c;  
    for (int i = 0, t = 0; i < a.size(); ++i) {  
        t = a[i] - t;//1. t = a[i] -b[i] -t;-t是因为考虑借位的情况, 这里的t只能是1或0  
        if (i < b.size()) t -= b[i];//这里因为b位数小于a,要判断一下b的位数是否存在  
        c.push_back((t + 10) % 10);//2. 将当前位插入数组  
        if (t < 0) t = 1; else t = 0;//3. 控制进位变量  
    }  
    while (c.size() > 1 && c.back() == 0)c.pop_back();//注意是逆序,抹除0需要用back()  
    return c;  
}  
  
void high_precision_sub() {  
    string a, b;  
    vector<int> A, B;  
    cin >> a >> b;// 123456 123456  
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');//654321  
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');//654321  
    vector<int> c;  
    if (compare(A, B)) {  
        c = sub(A, B);  
        for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);  
    } else {  
        c = sub(B, A);  
        printf("-");  
        for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);  
    }  
}

高精度乘法

vector<int> mul(vector<int> &A, int b) {  
    vector<int> c;  
    int t = 0;//进位  
    for (int i = 0; i < A.size() || t; ++i) {  
        if (i < A.size())t += A[i] * b;//用高精度的一位乘以普通数  
        c.push_back(t % 10);  
        t /= 10;  
    }  
    while (c.size() > 1 && c.back() == 0)c.pop_back();//注意是逆序,抹除0需要用back()  
    return c;  
}  
  
void high_precision_mul() {  
    string a;  
    int b;  
    vector<int> A;  
    cin >> a >> b;// 123456 3  
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');//654321  
    vector<int> c = mul(A, b);  
    for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);  
  
}

高精度除法

vector<int> div(vector<int> &A, int b, int &r) {  
    vector<int> c;  
    r = 0;  
    for (int i = A.size() - 1; i >= 0; i--) {  
        r = r * 10 + A[i];  
        c.push_back(r / b);  
        r %= b;  
    }  
    reverse(c.begin(), c.end());  
    while (c.size() > 1 && c.back() == 0)c.pop_back();  
    return c;  
}  
  
void high_precision_div() {  
    string a;  
    int b;  
    vector<int> A;  
    cin >> a >> b;// 123456 3  
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');//654321  
    int r;  
    vector<int> c = div(A, b, r);  
    for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);  
    cout << endl << r << endl;  
}