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

### 一、算法原理

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

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

数组中是这样存储的：
<center><img src='https://img2020.cnblogs.com/blog/8562/202109/8562-20210917094727724-1157818874.png'></center>

**倒序存储原因**：

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

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

<center> <img src='https://img2020.cnblogs.com/blog/8562/202109/8562-20210917095858016-1722478475.png'></center>


### 二、[$AcWing$ $791$. 高精度加法](https://www.acwing.com/problem/content/793/)

```cpp {.line-numbers}
#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$. 高精度减法](https://www.acwing.com/problem/content/794/)

```cpp {.line-numbers}
#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$. 高精度乘法](https://www.acwing.com/problem/content/795/)

```cpp {.line-numbers}
#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;
}

```

> **注**：网上对于高精度乘法，一般有高精乘低精 和 高精乘高精两种，学生们背起来太麻烦，容易出错，我把两个合并了一下，形成了一个模板，对于高精乘低精也可以兼容到，比如：
```cpp {.line-numbers}
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$. 高精度除法](https://www.acwing.com/problem/content/796/)

```cpp {.line-numbers}
#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$位
```cpp {.line-numbers}
// 高精乘高精,限长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--;
```