高精度乘法

高精度乘低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// A 是大数（vector），b 是普通整数（int）
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int t = 0; // t 不仅是进位，也是当前计算的临时结果
    
    // 注意：这里的 t 可能很大，不仅仅是 0 或 1
    for (int i = 0; i < A.size() || t; i++) {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    
    // 去掉前导 0（比如 123 * 0 = 000，我们要变回 0）
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}


高精度乘高精度

这个公式的证明其实非常直观，它的核心在于十进制数值的展开式。

我们可以通过以下三个步骤来证明：

1. 数值的数学表示

任何一个多位整数都可以写成以 $10$ 为底的幂级数形式。
假设大整数 $A$ 有 $n$ 位，大整数 $B$ 有 $m$ 位：

$$A = A[0] \cdot 10^0 + A[1] \cdot 10^1 + A[2] \cdot 10^2 + \dots + A[i] \cdot 10^i$$
$$B = B[0] \cdot 10^0 + B[1] \cdot 10^1 + B[2] \cdot 10^2 + \dots + B[j] \cdot 10^j$$

其中 $A[i]$ 是 $A$ 从右往左数第 $i$ 位上的数字（即权重为 $10^i$ 的位）。

2. 乘法的展开（多项式乘法）

当我们计算 $A \times B$ 时，根据乘法分配律，相当于 $A$ 中的每一项都要乘以 $B$ 中的每一项：

$$A \times B = \left( \sum_{i=0}^{n} A[i] \cdot 10^i \right) \times \left( \sum_{j=0}^{m} B[j] \cdot 10^j \right)$$

展开后的每一项可以写成：
$$(A[i] \cdot 10^i) \times (B[j] \cdot 10^j) = (A[i] \times B[j]) \cdot 10^{i+j}$$

3. 指数定律的运用

注意看结果中的幂次部分：
$$10^i \times 10^j = 10^{i+j}$$

这告诉我们：$A$ 的第 $i$ 位与 $B$ 的第 $j$ 位相乘的结果，其权重是 $10^{i+j}$。

在我们的结果数组 $C$ 中，$C[k]$ 存储的就是权重为 $10^k$ 的部分。因此，所有满足 $i + j = k$ 的乘积项 $(A[i] \times B[j])$ 都应该累加到 $C[k]$ 上。

举个简单的例子：$12 \times 34$

  • $A = 12 = 1 \cdot 10^1 + 2 \cdot 10^0 \implies A[1]=1, A[0]=2$
  • $B = 34 = 3 \cdot 10^1 + 4 \cdot 10^0 \implies B[1]=3, B[0]=4$

我们来算 $C[i+j]$：

  1. 当 $i=0, j=0$：$i+j=0$。$C[0] = A[0] \times B[0] = 2 \times 4 = 8$
  2. 当 $i=0, j=1$：$i+j=1$。$C[1] += A[0] \times B[1] = 2 \times 3 = 6$
  3. 当 $i=1, j=0$：$i+j=1$。$C[1] += A[1] \times B[0] = 1 \times 4 = 4$（此时 $C[1] = 6+4=10$）
  4. 当 $i=1, j=1$：$i+j=2$。$C[2] = A[1] \times B[1] = 1 \times 3 = 3$

目前 $C$ 数组为：{8, 10, 3}（对应 $8 \cdot 10^0 + 10 \cdot 10^1 + 3 \cdot 10^2$）

最后处理进位：

  • $C[0]=8$
  • $C[1]=10 \implies$ 留 $0$，进 $1$
  • $C[2]=3 + 进位1 = 4$

结果为：$408$。 计算正确！

结论

这个公式的本质是：高精度乘法 = 多项式乘法 + 进位处理。
由于 $10^i \cdot 10^j = 10^{i+j}$，所以 $A[i] \cdot B[j]$ 必须且只能贡献给结果数组中的第 $i+j$ 位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> mul_big(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];
        }
    }
    
    // 最后统一处理进位
    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;
}

洛谷1303

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>

using namespace std;

  

vector<int> stringToV(string a){

    vector<int> n;

    int len=a.length();

    for(int i=len-1;i>=0;i--){

        int num=a[i]-'0';

        n.push_back(num);

    }

    return n;

}

  

vector<int> highMul(string s1,string s2){

    if(s1=="0" || s2=="0") return {0};

  

    vector<int> a=stringToV(s1);

    vector<int> b=stringToV(s2);

  

    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];

        }

    }

  

    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;

}

  

int main(){

    string a,b;

    cin>>a>>b;

    vector<int> ans=highMul(a,b);

    for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];

    cout<<endl;

    return 0;

}

高精度加法

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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 高精度加法函数
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0; // t 代表进位

    for (int i = 0; i < A.size() || i < B.size(); i++) {
        // 如果 A 还没加完，就把 A[i] 加到 t
        if (i < A.size()) t += A[i];
        // 如果 B 还没加完，就把 B[i] 加到 t
        if (i < B.size()) t += B[i];
        
        C.push_back(t % 10); // 当前位的结果
        t /= 10;             // 计算新的进位
    }

    if (t) C.push_back(t);   // 最后如果还有进位，补上
    return C;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2; // 读入两个巨大的数字

    vector<int> A, B;
    // 倒序存入 vector：'123' -> {3, 2, 1}
    for (int i = s1.size() - 1; i >= 0; i--) A.push_back(s1[i] - '0');
    for (int i = s2.size() - 1; i >= 0; i--) B.push_back(s2[i] - '0');

    vector<int> C = add(A, B);

    // 输出时也要倒着输出：{6, 5, 1} -> 156
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    
    return 0;
}