本篇将介绍高精度算法

简介

高精度计算运用算法结构，来支持更大区间的数字运算。
基本思想是通过模拟各位计算，用来作为模拟算法的练习较为不错。

存储&输入输出

一般的数字，我们使用int/long/long long进行存储，但是大区间的数字未必存的下。针对这个问题，我们使用字符串读取高精度数字。

在计算的时候，为了模拟我们小学的时候学的竖式运算，我们会将每一位分开存储，且从小到大计算。所以在数组中下标小的存放的是数字的 最低位。而在字符串中默认使用左高右低的十进制写法，当我们存储到数组中的时候，就需要「反转存储」

注：作者后续都会使用vector向量的写法，实际上使用任意一维数组都可以
由此易得高精度输入和输出的代码：

1
2
3
4
5
6
7
8
9
10
void read(vector<int> *a) {
	string s;
	cin >> s;
	for(int i = s.size() - 1;i >= 0;i--) a.push_back(s[i]); //反转存储
}

void print(vector<int> a) {
    while(a.size() && a.back() == 0) a.pop_back(); //删除所有的前导零
	for(int i = a.size() - 1;i >= 0;i--) cout << a[i]; //逆序输出
}

四则运算

四则运算的难度不同，我们将从易到难进行讲解

加法

高精度加法即为对竖式运算的模拟

从最低位开始，将两个同样位置的数字相加，并判断是否大于10，如果大于则需要考虑进位。
进位则将更高一位的结果上加1，当前位结果减10。

1
2
3
4
5
6
7
8
9
10
11
12
13
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]; // 判断B是否够长 
		C.push_back(t % 10);
		t /= 10;
	}
	if (t) C.push_back(t);
	return C;
}

减法

减法依旧是对竖式减法的模拟

从最低位开始，将两个同样位置的数字相减，遇到负数则考虑借位。
借位则需要向上一位借1，当前位加10。
和加法不同的是，我们这里需要判断减数和被减数的大小，来选择是否输出负号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 false;
}

vector<int> sub(vector<int> A, vector<int> B) {
	if (cmp(A,B)) {
		cout << '-';
		return sub(B,A);
    }
	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+10是为了避免t<0 
        if(t < 0) t = 1; // 借位 
        else t = 0; // 不借位 
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();  //去掉前导0
    return C;
}

乘法

乘法的竖式运算实际上是计算了每一位相乘的和，例如：47×32=7×2+40×2+7×30+40×3047\times32=7\times2+40\times2+7\times30+40\times30
于是我们可以将两个高精度数字的每一位数码相乘，并加到他们数位之和的位置

1
2
3
4
5
6
7
8
9
10
11
12
vector <int> mul(vector <int> &A, vector <int> &B) {
    vector <int> C(A.size() + B.size(), 0); //初始化答案向量大小
    for (int i = 0; i < A.size(); i ++) {
	    for (int j = 0; j < B.size(); j ++){
		    C[i + j] += A[i] * B[j];
		    C[i + j + 1] += C[i + j] / 10;
		    C[i + j] %= 10;
		}
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); //删去前导零
    return C;
}

除法

关于竖式除法实际上可以看作数个减法的过程。
∵324=12×20+12×7\because324=12\times20+12\times7
∴324÷12=20+7=27\therefore324\div12=20+7=27
当除数大于被除数时，被除数就是余数。当被除数大于除数时，我们可以从 l被除数−l除数l_{被除数}-l_{除数} 的位置开始依次从被除数中减去除数，减去的个数就是对应位数的答案，这里需要使用前面提到的高精度减法的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
    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);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

vector<int> div(vector<int> A, vector<int> B, vector<int> &R) {
    //A=被减数 B=减数 R=余数
    vector<int> C; //初始化答案向量
    R.clear();
    R.push_back(0);
	// 从最高位开始，逐位试商
    for (int i = A.size() - 1; i >= 0; i--) {
        R.insert(R.begin(), A[i]);
        while (R.size() > 1 && R.back() == 0) R.pop_back(); // 去前导0
        int q = 0;
        while (cmp(R, B)) {
            R = sub(R, B);
            q++;
        }
        C.push_back(q);
    }
    reverse(C.begin(), C.end()); // 答案现在是高位在前，翻转成低位在前
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去前导0
    return C;
}

完成

xxxxxxxxxx #include <bits/stdc++.h>using namespace std;const int N = 101, M = 1e9+7;​int n;long long k;​struct mat { int c[N][N]; mat operator* (const mat a) const {     mat res;     for(int i = 0;i < N;i++) {         for(int j = 0;j < N;j++) {             for(int l = 0;l < N;l++) {                 res.c[i][j] = (res.c[i][j] + 1LL * c[i][l] * a.c[l][j]) % M;             }         }     }     return res; } mat() {memset(c, 0, sizeof(c));}} ans, a;​void quick(long long k) { while(k) {     if(k&1) ans = ans * a;     a = a * a;     k >>= 1; }}​signed main(){ cin >> n >> k; for(int i = 0;i < n;i++) ans.c[i][i] = 1; for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) cin >> a.c[i][j]; quick(k); for(int i = 0;i < n;i++) {     for(int j = 0;j < n;j++) cout << ans.c[i][j] << " ";     cout << endl; } return 0;}cpp