为什么用高精度计算？

32 位计算机有符号整数（int）的取值范围是：

32 位计算机无符号整数（unsigned int）的取值范围是：

那么我们进一步思考，如果数据类型更大呢？可以使用 long long，但是还有没有更大的数据类型？

而所谓的高精度运算，是指在某些问题中，参与处理的数据大小超出了标准数据类型所能表示的范围的运算。

高精度运算是信息学比赛中用到的最基础的知识之一，单独考察的情形很少出现。但作为基础知识，在考察其他主要算法时会经常用到。且常出现在难度较高的题目中，要求选手具有较高的编程技巧和程序调试能力。

高精度存储

高精度数每一位数字存储在一个数组中。

例：请用字符数组方法输入两个高精度数 9753186420321

123456789

char s1[N], s2[N];cin >> s1 >> s2;cout << s1 << endl << s2 << endl;

字符数组转整数数组：

方法一：前面元素从低位开始存储

方法二：前面元素存储大数低位，后面元素存储大数高位

方法三：第一个元素存储大数长度

然而，在我们实际解题过程中，经常是将高精度问题融入到一个其它类型算法当中，比如，高精度的斐波那契数列问题，就需要连续使用高精度加法，因此，我们将高精度算法都使用函数封装起来，参数和返回值都用vector类型，方便在各种情况下进行调用高精度运算。

高精度加法

位数相同无进位

位数不同无进位

位数不同有进位

#include <iostream>  #include <string>#include <vector>using namespace std; string str1, str2;vector<int> A, B;vector<int> add(vector<int>& A, vector<int>& B){    vector<int> C;    if(A.size() < B.size()) return add(B, A);    int k = 0; // 进位    for(int i = 0; i < A.size(); i++){        int t = A[i] + k;        if(i < B.size()) t += B[i];        C.push_back(t % 10);        k = t / 10;    }    if(k) C.push_back(1);    while(C.back() == 0 && C.size() > 1) C.pop_back();    return C;}int main(){    cin >> str1 >> str2;    for(int i = str1.size() - 1; i >= 0; i--) A.push_back(str1[i] - '0');    for(int i = str2.size() - 1; i >= 0; i--) B.push_back(str2[i] - '0');    auto C = add(A, B);    for(int i = C.size() - 1; i >= 0; i--)        cout << C[i];    return 0;}

位数相同无借位

位数不同无借位

位数不同有借位

#include <iostream>  #include <string>#include <vector>using namespace std; string str1, str2;vector<int> A, B;// A >= Bbool 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 k = 0; // 借位    for(int i = 0; i < A.size(); i++){        int t = A[i] - k;        if(i < B.size()) t -= B[i];        C.push_back((t + 10) % 10);        if(t < 0) k = 1;        else k = 0;    }    while(C.back() == 0 && C.size() > 1) C.pop_back();    return C;}int main(){    cin >> str1 >> str2;    for(int i = str1.size() - 1; i >= 0; i--) A.push_back(str1[i] - '0');    for(int i = str2.size() - 1; i >= 0; i--) B.push_back(str2[i] - '0');    if(cmp(A, B)){        auto C = sub(A, B);        for(int i = C.size() - 1; i >= 0; i--)            cout << C[i];    }     else{        auto C = sub(B, A);        cout << "-";        for(int i = C.size() - 1; i >= 0; i--)            cout << C[i];    }    return 0;}

高精度数字的每一位乘低精度数字，而后不断进位。

#include <iostream>#include <cstdio>#include <string>#include <vector>using namespace std;string s1;vector<int> A;int b;vector<int> mul(vector<int>& A, int b) {    vector<int> C;    int k = 0;    for (int i = 0; i < A.size() || k; i++) {        int t;        if (i < A.size()) t = A[i] * b + k;        else t = k;        k = t / 10;        C.push_back(t % 10);    }    while (!C.back() && C.size() > 1) C.pop_back();    return C;}int main() {    cin >> s1 >> b;    for (int i = s1.size() - 1; i >= 0; i--) A.push_back(s1[i] - '0');    vector<int> C = mul(A, b);    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];    return 0;}

#include <iostream>#include <cstdio>#include <vector>#include <string>using namespace std;string s1, s2;vector<int> A, B, C;vector<int> mul(vector<int>& A, vector<int>& B) {    vector<int> C(A.size() + B.size() + 10);    for (int i = 0; i < B.size(); i++)        for (int j = 0; j < A.size(); j++)            C[i + j] += B[i] * A[j];    int t = 0;    for (int i = 0; i < C.size(); i++) {        t += C[i];        C[i] = t % 10;        t /= 10;    }    while (!C.back() && C.size() > 1) C.pop_back();    return C;}int main() {    cin >> s1 >> s2;    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');    C = mul(A, B);    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];    return 0;}

将商存储在 c 数组中，余数存储在变量 r 中。

#include <iostream>#include <cstdio>#include <string>#include <vector>#include <algorithm>using namespace std;string s1;int b, r = 0;vector<int> A;vector<int> div(vector<int>& A, int b, int& r) {    vector<int> C;    for (int i = 0; i < A.size(); i++) {        int t = r * 10 + A[i];        C.push_back(t / b);        r = t % b;    }    reverse(C.begin(), C.end());    while (!C.back() && C.size() > 1) C.pop_back();    return C;}int main() {    cin >> s1 >> b;    for (int i = 0; i < s1.size(); i++) A.push_back(s1[i] - '0');    vector<int> C = div(A, b, r);    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];    // cout << endl << r << endl;    return 0;}

#include <iostream>#include <cstdio>#include <string>#include <vector>#include <algorithm>using namespace std;string s1, s2;vector<int> A, B, R;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;    if (!cmp(A, B)) {        cout << "-";        return sub(B, A);    }    int k = 0;    for (int i = 0; i < A.size(); i++) {        int t = A[i] - k;        if (i < B.size()) t -= B[i];        C.push_back((t + 10) % 10);        if (t < 0) k = 1;        else k = 0;    }    while (!C.back() && C.size() > 1) C.pop_back();    return C;}vector<int> div(vector<int>& A, vector<int>& B, vector<int>& R) {    vector<int> C;    int j = B.size();    R.assign(A.end() - j, A.end());    while (j <= A.size()) {        int k = 0;        while (cmp(R, B)) {            vector<int> tmp = sub(R, B);            R.assign(tmp.begin(), tmp.end());            k++;        }        C.push_back(k);        if (j < A.size()) R.insert(R.begin(), A[A.size() - j - 1]);        while (!R.back() && R.size() > 1) R.pop_back();        j++;    }    reverse(C.begin(), C.end());    while (!C.back() && C.size() > 1) C.pop_back();    return C;}int main() {    cin >> s1 >> s2;    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');    if(!cmp(A, B)){        cout << 0 << endl;        cout << s1 << endl;        return 0;    }    vector<int> C = div(A, B, R);    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];    cout << endl;    for (int i = R.size() - 1; i >= 0; i--) cout << R[i];    return 0;}