C++ 中，

  • int 类型为 32 为，表示上限为 5.6 高精度 - 图1
  • long long 类型为 64 位，表示上限为 5.6 高精度 - 图2

二者可通过 unsigned 修饰取消负数，可以将正整数表示范围扩大一倍。

程序经常出现 int 不足以存储答案的情况，此时使用 long long 类型。

  1. #include <iostream>
  2. using namespace std;
  3. typedef long long ll;
  4. // typedef long long LL; 大小写为个人习惯
  5. ll ans;        // long long 类型变量

部分时候，在完成整个程序后，你发现程序需要使用 long long ，而程序中已经遍布 int ，此时有一招补救措施。

#include <iostream>
// 注意 define 语句没有结尾分号
#define int long long
using namespace std;
// signed 暗指 int类型
signed main() {
}

这样一来，程序中所有 int 类型均为 long long 类型，而 main 规定必须为 int 类型，使用 signed 代替。

少数情况下，计算过程中出现超过 long long 类型上限的整数，则需要使用高精度计算。如果使用 Java，请直接使用 BigInteger 类型。如果题目并不复杂，可以考虑使用 Python。

高精度的一般思路是用数组进行模拟，每个数组元素为十进制的一位数字。

下文将提供高精度的模板，请根据需求使用（如果题目只做加法，就只写高精度加法的板子）。

5.6.1 高精度加减乘除 *

模板演示

#include <bits/stdc++.h>
using namespace std;
vector<int> A, B;    // 数组模拟大整数

void read(vector<int>& A) {
    string s;
    cin >> s;
    for (int i=s.size()-1; i>=0; --i) {
        A.push_back(s[i] - '0');
    }
}
// @overload 从字符串输入
void read(vector<int>& A， string s) {
    for (int i=s.size()-1; i>=0; --i) {
        A.push_back(s[i] - '0');
    }
}
void print(vector<int>& A) {
    for (int i=A.size()-1; i>=0; --i) {
        cout << A[i];
    }
}
// 判断是否 A >= B，用于减法
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;    // A == B
}
vector<int> add(vector<int>& A, vector<int>& B) {
    if (A.size() < B.size()) {
        return add(B, A);
    }
    vector<int> C;
    int t = 0;
    for (int i=0; i<A.size(); ++i) {
        t += A[i];
        if (i < B.size()) {
            t += B[i];
        }
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) {
        C.push_back(1);
    }
    return C;
}
// A 必须大于 B, 否则请计算 -1 * sub(B, A) 
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);
        t = t < 0 ? 1 : 0;
    }
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    return C;
}
// 高精 * 低精
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();
    }
    return C;
}
// @overload 高精 * 高精 （很少使用）
vector<int> mul(vector<int>& A, vector<int>& B) {
    vector<int> C(A.size() + B.size());
    for (int i=0; i<A.size(); ++i) {
        for (int j=0; j<B.size(); ++j) {
            C[i + j] += A[i] * B[i];
        }
    }
    int t = 0;
    for (int i=0; i<C.size(); ++i) {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    return C;
}
// 高精 / 低精，@r 为余数
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;
}
int main() {
    read(A);
    read(B);
    // 加
    auto C = add(A, B);
    cout << "A + B = ";
    print(C);
    cout << endl;
    // 减
    cout << "A - B = ";
    if (cmp(A, B)) {
        C = sub(A, B);
        print(C);
    } else {
        C = sub(B, A);
        cout << '-';
        print(C);
    }
    cout << endl;
    // 乘
    C = mul(A, 2);
    cout << "A * 2 = ";
    print(C);
    cout << endl;
    // 除
    int r = 0;      // 传入引用型参数前，必须声明
    C = div(A, 2, r);
    cout << "A / 2 = ";
    print(C);
    cout << " 余 " << r << endl;
    return 0;
}
  • 此模板参考 AcWing 公开的高精度计算模板

C++ 允许「重载」函数，本篇在代码中用 @overload 标记。使用有重载的函数模板，可以根据需求选择写一个或多个。

例题：蓝桥 基础练习 阶乘计算

你可以直接按照模板写，用 to_string读入 A（蓝桥评测不开 C++11 有点麻烦），也可以自己再写一个输入。（如果你完全领会模板，你完全可以灵活改变它。也就是说，算法从来不是套模板这么简单）

参考代码

写 to_str() ，并使用模板读入：

#include <bits/stdc++.h>
using namespace std;
vector<int> A;
int n;
// C++11 前没有 to_string，自己写一个
string tostr(int n) {
    string res;
    while (n) {
        res += '0' + (n % 10);
        n /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}
void read(vector<int>& A, string s) {
    for (int i=s.size()-1; i>=0; --i) {
        A.push_back(s[i] - '0');
    }
}
void print(vector<int>& A) {
    for (int i=A.size()-1; i>=0; --i) {
        cout << A[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();
    }
    return C;
}
int main() {
    cin >> n;
    read(A, tostr(n));
    while (--n) {
        A = mul(A, n);
    }
    print(A);
    cout << endl;
    return 0;
}

自己重新写输入：

#include <bits/stdc++.h>
using namespace std;
vector<int> A;
int n;
// 注意这个数组 A 存放的数，排列上是反的，即 123 存为 {3, 2, 1}
// 未知模板意图时，可通过调试验证
void read(vector<int>& A, int x) {
    while (x) {
        A.push_back(x % 10);
        x /= 10;
    }
}
void print(vector<int>& A) {
    for (int i=A.size()-1; i>=0; --i) {
        cout << A[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();
    }
    return C;
}
int main() {
    cin >> n;
    read(A, n);
    while (--n) {
        A = mul(A, n);
    }
    print(A);
    cout << endl;
    return 0;
}

5.6.2 大整数类模板 *

在题目重点考察高精度计算时，我们有时需要花些时间写出完整的大整数类，重载操作符，在调用时比较方便。注意，模板为 ACM 竞赛使用，并非背诵材料。

参考：高精度计算，文末有模板。