python/TangDou/AcWing/HighPrecision/高精度模板.md

一、算法原理

1. 当输入的数很大时，可采用字符串方式接收。

2. 拆成一位一位的数字，把它们存在一个数组中，一个数组元素表示一位数字

数组中是这样存储的：

倒序存储原因：

在平常，数字从左到右依次为从高位到低位....可这里却与日常的习惯相反。

这是因为加法可能会产生进位，而数组在最前面加上数字是不可能的，但在尾巴处加上数字是好做的，所以，倒着放。

二、AcWing 791. 高精度加法

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;

int a[N], b[N];
int al, bl;
void add(int a[], int &al, int b[], int &bl) {
    int t = 0;
    al = max(al, bl);
    for (int i = 0; i < al; i++) {
        t += a[i] + b[i];
        a[i] = t % 10;
        t /= 10;
    }
    if (t) a[al] = 1;
    while (al > 0 && a[al] == 0) al--;
}

int main() {
    string x, y;
    cin >> x >> y;
    for (int i = x.size() - 1; i >= 0; i--) a[al++] = x[i] - '0';
    for (int i = y.size() - 1; i >= 0; i--) b[bl++] = y[i] - '0';
    add(a, al, b, bl);
    for (int i = al; i >= 0; i--) printf("%d", a[i]);
    return 0;
}

三、AcWing 792. 高精度减法

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], al;
int b[N], bl;

void sub(int a[], int &al, int b[], int &bl) {
    int t = 0;
    al = max(al, bl);
    for (int i = 0; i < al; i++) {
        t = a[i] - b[i] - t;
        a[i] = (t + 10) % 10;
        t < 0 ? t = 1 : t = 0;
    }
    while (al > 0 && a[al] == 0) al--;
}

int main() {
    string x, y;
    cin >> x >> y;

    // 负号
    if (x.size() < y.size() || (x.size() == y.size() && x < y)) {
        printf("-");
        swap(x, y);
    }

    for (int i = x.size() - 1; i >= 0; i--) a[al++] = x[i] - '0';
    for (int i = y.size() - 1; i >= 0; i--) b[bl++] = y[i] - '0';

    sub(a, al, b, bl);

    for (int i = al; i >= 0; i--) printf("%d", a[i]);
    return 0;
}

四、AcWing 793. 高精度乘法

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int a[N], al;
int b[N], bl;
void mul(int a[], int &al, int b[], int &bl) {
    int t = 0;
    int c[N] = {0};
    for (int i = 0; i < al; i++)
        for (int j = 0; j < bl; j++)
            c[i + j] += a[i] * b[j];
    al += bl;
    for (int i = 0; i < al; i++) {
        t += c[i];
        a[i] = t % 10;
        t /= 10;
    }
    // 前导0
    while (al > 0 && a[al] == 0) al--;
}

int main() {
    string x, y;
    cin >> x >> y;
    for (int i = x.size() - 1; i >= 0; i--) a[al++] = x[i] - '0';
    for (int i = y.size() - 1; i >= 0; i--) b[bl++] = y[i] - '0';

    mul(a, al, b, bl);
    for (int i = al; i >= 0; i--) printf("%d", a[i]);
    return 0;
}

注：网上对于高精度乘法，一般有高精乘低精 和 高精乘高精两种，学生们背起来太麻烦，容易出错，我把两个合并了一下，形成了一个模板，对于高精乘低精也可以兼容到，比如：

int main() {
    string x;
    int y;
    cin >> x >> y;
    for (int i = x.size() - 1; i >= 0; i--) a[al++] = x[i] - '0';
    b[0] = y, bl = 1;
    mul(a, al, b, bl);
    for (int i = al; i >= 0; i--) printf("%d", a[i]);
    return 0;
}

五、AcWing 794. 高精度除法

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], al, r;
void div(int a[], int &al, int b, int &r) {
    r = 0;
    for (int i = al - 1; i >= 0; i--) {
        r = r * 10 + a[i];
        a[i] = r / b;
        r %= b;
    }
    // 去前导0
    while (al > 0 && !a[al]) al--;
}

int main() {
    string x;
    int y;

    cin >> x >> y;

    for (int i = x.size() - 1; i >= 0; i--) a[al++] = x[i] - '0';
    // 高精度除法
    div(a, al, y, r);

    // 输出
    for (int i = al; i >= 0; i--) printf("%d", a[i]);
    puts("");
    printf("%d\n", r);
    return 0;
}

六、保留结果K位

// 高精乘高精,限长K(K<=100,不是很大)
void mul(int a[], int b[]) {
    int t = 0;
    int c[N] = {0};
    for (int i = 0; i < K; i++)
        for (int j = 0; j < K; j++)
            if (i + j < K) c[i + j] += a[i] * b[j]; // 防止越界，需要加上i+j<K的限制

    for (int i = 0; i < K; i++) {
        t += c[i];     // 进位与当前位置的和
        a[i] = t % 10; // 余数保留下来
        t /= 10;       // 进位
    }
}

// 去前导0
//int al=K;
//while (al > 0 && a[al]==0) al--;