第一讲 基础算法 - 04 高精度

[toc]

AcWing 791. 高精度加法C++数组实现 - AcWing
高精度模板汇总-实用 - AcWing
AcWing 高精度模板 - 糖豆爸爸 - 博客园
AcWing《算法基础课》第1章 算法基础 - AcWing
AcWing 算法基础课笔记 1.基础算法-CSDN博客
A01 高精度算法 加法_哔哩哔哩_bilibili

---

高精度

高精度计算实际上用数组存储和模拟运算.
高精度计算也被称为大整数计算

1 大整数的存储

1. 当输入的数很大时，可采用字符串方式接收。
2. 拆成一位一位的数字，把它们存在一个数组中，一个数组元素表示一位数字

数组中是这样存储的：逆序存储

数组下标	a[0]	a[1]	a[2]	a[3]	a[4]	a[5]
原数	1	2	3	4	5	-
存储数	5	4	3	2	1	-

倒序存储原因：
因为整数运算大都是从低位到高位运算的，即数字是高位在前、低位在后，而数组是低位在前、高位在后，所以要倒序存储. 这样当遇到进位等情况时，当最高位要进位的时候，我们在数组的末尾使用 push_back() 加一位即可，较方便。反之，在头部加一位要将整个数组后移，较麻烦。

• 大整数低位存放在数组低地址处，高位存放在数组高地址处
  • 数组地址由低位到高位 （0 → n - 1）
  • 整数位数最左边是高位，最右边是低位 （高位→低位）
• 读取数组时反向 (n - 1 → 0) 遍历，运算时正向 (0 → n - 1) 遍历

2 大整数比较

2.1 数组

~i 等价于 i >= 0

int la, lb;

bool cmp(int A[], int B[]){
    if (la != lb) return la > lb;
    for (int i = la - 1; ~i; i -- )
        if (A[i] != B[i]) return A[i] > B[i];
    return true;    // 避免结果为 -0
}

2.2 vector

typedef vector<int> VI;

bool cmp(VI &A, VI &B){
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; ~i; i -- )
        if (A[i] != B[i]) return A[i] > B[i];
    return true;    // 避免结果为 -0
}

3 高精度加法

时间复杂度: O(n)
算法步骤:

1. 高精度数字利用字符串读入
2. 把字符串翻转存入两个整型数组 A, B
3. 从低位到高位, 累加, 进位, 存余 *
4. 把数组 C 从高位到低位依次输出

3.1 数组

const int N = 1e5 + 10;
int A[N], B[N], C[N];   // 表示三个大整数
int la, lb, lc;         // 数组的实际大小/长度

void add(int A[], int B[], int C[]){
    for (int i = 0; i < lc; i ++ ){
        C[i] += A[i] + B[i];        // 累加
        C[i + 1] += C[i] / 10;      // 进位
        C[i] %= 10;                 // 存余
    }
    if (C[lc]) lc ++ ;      // 处理最高位
}

int main()
{
    string a, b;
    cin >> a >> b;
    la = a.size(), lb = b.size(), lc = max(la, lb);
    for (int i = la - 1; ~i; i -- ) A[la - 1 - i] = a[i] - '0';     // 翻转存入数组 A
    for (int i = lb - 1; ~i; i -- ) B[lb - 1 - i] = b[i] - '0';     // 翻转存入数组 B
    add(A, B, C);
    for (int i = lc - 1; ~i; i -- ) printf("%d", C[i]);     // 倒序输出数组 C
    
    return 0;
}

3.2 vector

typedef vector<int> VI;
VI A, B, C;
void add(VI &A, VI &B, VI &C);

int main(void)
{
    string a, b;
    cin >> a >> b;
    for (int i = a.size() - 1; ~i; i -- ) A.push_back(a[i] - '0');      // 翻转存入 A
    for (int i = b.size() - 1; ~i; i -- ) B.push_back(b[i] - '0');      // 翻转存入 B
    add(A, B, C);
    for (int i = C.size() - 1; ~i; i -- ) cout << C[i];     // 倒序输出
    
    return 0;
}

void add(VI &A, VI &B, VI &C){
    int t = 0;      // 由 t 进行累加
    for (int i = 0; i < A.size() || i < B.size(); i++){
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);    // 存余
        t /= 10;                // 进位
    }
    if (t) C.push_back(t);      // 处理最高位
}

4 高精度减法

时间复杂度: O(n)
算法步骤:

1. 高精度数组利用字符串读入
2. 把字符串翻转存入两个整型数组 A, B
3. 若 A < B, 则交换 A, B, 输出负号 *
4. 从低位到高位, 逐位求差, 借位, 存差 *
5. 把数组 C 从高位到低位依次输出

4.1 数组

const int N = 1e5 + 10;
int A[N], B[N], C[N];
int la, lb, lc;
bool cmp(int A[], int B[]);
void sub(int A[], int B[], int C[]);

int main(void)
{
    string a, b;
    cin >> a >> b;
    la = a.size(), lb = b.size(), lc = max(la, lb);
    for (int i = la - 1; ~i; i -- ) A[la - 1 - i] = a[i] - '0';     // 翻转存入 A
    for (int i = lb - 1; ~i; i -- ) B[lb - 1 - i] = b[i] - '0';     // 翻转存入 B
    if (!cmp(A, B)) swap(A, B), cout << '-';    // 若 A < B, 则交换 A, B, 输出负号
    sub(A, B, C);
    for (int i = lc; ~i; i -- ) cout << C[i];
    
    return 0;
}

bool cmp(int A[], int B[]){
    if (la != lb) return la > lb;
    for (int i = la - 1; ~i; i -- )
        if (A[i] != B[i]) return A[i] > B[i];
    return true;    // 避免结果为 -0
}

void sub(int A[], int B[], int C[]){
    for (int i = 0; i < lc; i ++ ){
        if (A[i] < B[i])
            A[i + 1] --, A[i] += 10;    // 借位
        C[i] = A[i] - B[i];             // 存差
    }
    while (lc && C[lc] == 0) lc--;      // 处理前导0
}

4.2 vector

typedef vector<int> VI;
VI A, B, C;
bool cmp(VI &A, VI &B);
void sub(VI &A, VI &B, VI &C);

int main(void)
{
    string a, b;
    cin >> a >> b;
    for (int i = a.size() - 1; ~i; i -- ) A.push_back(a[i] - '0');      // 翻转存入 A
    for (int i = b.size() - 1; ~i; i -- ) B.push_back(b[i] - '0');      // 翻转存入 B
    if (!cmp(A, B)) swap(A, B), cout << "-";        // 若 A < B, 则交换 A, B, 输出负号
    sub(A, B, C);
    for (int i = C.size() - 1; ~i; i -- ) cout << C[i];
    
    return 0;
}

bool cmp(VI &A, VI &B){
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; ~i; i -- )
        if (A[i] != B[i]) return A[i] > B[i];
    return true;    // 避免结果为 -0
}

void sub(VI &A, VI &B, VI &C){
    int t = 0;      // t 存储借位
    for (int i = 0; i < A.size(); i++){
        t = A[i];
        if (i < B.size()) t -= B[i];
        if (t < 0) A[i + 1] --, t += 10;    // 借位
        C.push_back(t);                     // 存余
    }
    while (C.size() > 1 && !C.back()) C.pop_back();     // 处理前导0
}

5 高精度乘法

时间复杂度 : O(n^2)
算法步骤:

1. 高精度数组利用字符串读入
2. 把字符串翻转存入两个整型数组 A, B
3. 从低位到高位, 累加乘积, 进位, 存余 *
4. 把数组 C 从高位到低位依次输出

5.1 数组

const int N = 1e5 + 10;
int A[N], B[N], C[N];
int la, lb, lc;
void mul(int A[], int B[], int C[]);

int main(void)
{
    string a, b;
    cin >> a >> b;
    la = a.size(), lb = b.size(), lc = la + lb;
    for (int i = la - 1; ~i; i -- ) A[la - 1 - i] = a[i] - '0';     // 翻转存入
    for (int i = lb - 1; ~i; i -- ) B[lb - 1 - i] = b[i] - '0';     // 翻转存入
    mul(A, B, C);
    for (int i = lc; ~i; i -- ) cout << C[i];       // 逆序输出
    
    return 0;
}

void mul(int A[], int B[], int C[]){
    for (int i = 0; i < la; i ++ )
        for (int j = 0; j < lb; j ++ ){
        C[i + j] += A[i] * B[j];            // 累加乘积
        C[i + j + 1] += C[i + j] / 10;      // 进位
        C[i + j] %= 10;                     // 存余
    }
    while (lc && C[lc] == 0) lc -- ;        // 处理前导0（当有一个数为0时）
}

5.2 vector

C 的初始化:

// 其一
VI A, B;
int main()
{
    VI C(A.size() + B.size());
}

// 其二
VI A, B, C;
int main()
{
    C.resize(A.size() + B.size());
}

---

typedef vector<int> VI;
VI A, B, C;
void mul(VI &A, VI &B, VI &C);

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string a, b;
    cin >> a >> b;
    for (int i = a.size() - 1; ~i; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; ~i; i -- ) B.push_back(b[i] - '0');
    C.resize(A.size() + B.size());
    mul(A, B, C);
    for (int i = C.size() - 1; ~i; i -- ) cout << C[i];
    
    return 0;
}

void mul(VI &A, VI &B, VI &C){
    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()) C.pop_back();     // 处理前导0（当有一个数为0时）
}

6 高精度除法

大整数 ÷ 小整数.

时间复杂度: O(n)
算法步骤:

1. 高精度数组利用字符串读入
2. 把字符串翻转存入两个整型数组 A, B
3. 从高位到低位, 当前被除数, 存商, 求余数 *
4. 把数组 C 从高位到低位依次输出

6.1 数组

typedef long long LL;
LL r;       // 计算当前被除数，或者说余数
const int N = 1e5 + 10;
int A[N], b, C[N];
int la, lc;
void div(int A[], int b, int C[]);

int main(void)
{
    string a;
    cin >> a >> b;
    la = lc = a.size();
    for (int i = la - 1; ~i; i -- ) A[la - 1 - i] = a[i] - '0';     // 翻转存入
    div(A, b, C);
    for (int i = lc; ~i; i -- ) cout << C[i];       // 逆序输出
    cout << endl << r << endl;
    
    return 0;
}

void div(int A[], int b, int C[]){
    r = 0;
    for (int i = la - 1; ~i; i -- ){
        r = r * 10 + A[i];          // 被除数
        C[la - 1 - i] = r / b;      // 存商
        r %= b;                     // 余数
    }
    reverse(C, C + lc);
    while (lc && C[lc] == 0) lc -- ;    // 处理多余0
}

6.3 vector

typedef long long LL;
typedef vector<int> VI;
LL r;       // 计算当前被除数，或者说余数
VI A, C; int b;
void div(VI &A, int b, VI &C);

int main(void)
{
    string a;
    cin >> a >> b;
    for (int i = a.size() - 1; ~i; i -- ) A.push_back(a[i] - '0');      // 翻转存入
    div(A, b, C);
    for (int i = C.size() - 1; ~i; i -- ) cout << C[i];     // 逆序输出
    cout << endl << r << endl;
    
    return 0;
}

void div(VI &A, int b, VI &C){
    r = 0;
    for (int i = A.size() - 1; ~i; i -- ){
        r = r * 10 + A[i];      // 被除数
        C.push_back(r / b);     // 存商
        r %= b;                 // 余数
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && !C.back()) C.pop_back();     // 处理多余0
}

---

---

AcWing 791. 高精度加法C++数组实现 - AcWing
AcWing 791. 高精度加法 - AcWing
AcWing 792. 高精度减法 - AcWing
AcWing 793. 高精度乘法 - AcWing
AcWing 794. 高精度除法 - AcWing

7 yxc

7.1 高精度加法:

比如：1234 + 567 模拟一下：

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)     // 默认 A > B
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;      // t 存储进位
    for (int i = 0; i < A.size(); i ++ ){   // 以位数较大的 A 来遍历
        t += A[i];
        if (i < B.size()) t += B[i];        // 如果 B 还有剩余（A：1234，B：12）
        C.push_back(t % 10);    // 把进位尾接到 C
        t /= 10;
    }

    if (t) C.push_back(t);      //如果循环后仍有进位，则将其作为最后一位添加到 C 中
    return C;
}

说明：

• 这里 t 存储进位 1
• 模板假设 A 和 B 都是非负大整数，即 A ≥ 0，B ≥ 0
• 假设大整数的位数 A ≥ B，不满足要交换参数次序
• 注意处理最高位进位（循环中，循环结束之后）
• 读取数组时反向 (n - 1 → 0) 遍历，运算时正向 (0 → n - 1) 遍历
• 高精度加法不会出现前导 0，而减法、乘法和除法会出现前导 0

7.2 高精度减法:

这里用大数减小数，若 A < B，则计算 -(B-A) 。因为 A 和 B 存在数组里，不能直接比大小，所以需要写一个 cmp() 函数进行比较，判断用谁减谁。

比如：1234 - 567 模拟一下：

// A >= B返回true，否则返回false
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;
}

// C = A - B, 满足 A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)     // 默认 A >= B
{
    vector<int> C;
    int t = 0;      // t 存储借位
    for (int i = 0; i < A.size(); i ++ ){
        t = A[i] - t;
        if (i < B.size()) t -= B[i];    // 如果 B 还有剩余（A：1234，B：12）
        C.push_back((t + 10) % 10);     // 涵盖 t 为正数负数两种情况
        if (t < 0) t = 1;               // 更新借位
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();   // 去掉前导0，但不能把结果 0 去掉
    return C;
}

说明：

• 这里 t 存储借位 1
• 模板假设 A和B 都是非负大整数，且 A ≥ B，可用 cmp() 模板判断是否满足 A ≥ B，不满足交换参数次序即可
• (t + 10) % 10 涵盖了 t 正负两种情况
  • t >= 0，说明不需要借位，(t + 10) % 10 得到 t 本身
  • t < 0，说明需要借位，(t + 10) % 10 得到 t + 10
• 减法会产生多个前导 0 （123 - 120 = 003）
  • 将 C 中的高位 0 给 pop_back() 掉。即：while (C.size() > 1 && C.back() == 0) C.pop_back();
  • 去掉前导 0 时，注意不能把结果 0 也去掉，即需要判断 C.size() > 1

7.3 高精度乘法:

// C = A * b, A >= 0, b >= 0
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;
}

说明:

• 模板假设 A 是非负大整数，b 是基本类型 int
• 乘法模板把对最高位的进位的处理翻到了 for 的循环条件中，这是与加法的主要区别。加法之所以能用一个 if 就能解决最高位的进位问题，是因为高精度加法最高位进位不会超过 10（实际上最多是 1），而高精度乘法的最高位进位可能超过 10，甚至更高，因此不能像加法那样处理

7.4 高精度除法:

// A / b = C ... r, A >= 0, b > 0
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;
}

说明：

• 模板假设 A 是非负大整数，b 是基本类型 int
• 商用 vector<int> 保存，余数用参数 r 保存
• 除法是反向遍历（高位到低位）
• 结果要翻转，注意导入 <algorithm> 库
• 注意遍历时，r = r * 10 + A[i]; 是 **=**，而不是 +=