acwing算法基础之基础算法--高精度乘法算法

1 知识点

大数乘以小数
大数的每一位与小数相乘

2 模板

自己实践出来的模板，

（1）字符串形式

//输入num1和num2，输出num1*num2的结果
//例如输入"123"和"456"，输出"56088"
//num1和num2都可以是大数
string multiply(string num1, string num2) {
    int n1 = num1.size();
    int n2 = num2.size();
    string result(n1 + n2, '0'); // 用于存储乘法结果的字符串

    // 从右往左遍历 num1 的每一位数字
    for (int i = n1 - 1; i >= 0; i--) {
        int carry = 0;
        int digit1 = num1[i] - '0';

        // 从右往左遍历 num2 的每一位数字
        for (int j = n2 - 1; j >= 0; j--) {
            int digit2 = num2[j] - '0';

            // 计算乘积，并加上之前的进位
            int product = digit1 * digit2 + carry;

            // 更新当前位和进位
            int temp = result[i + j + 1] - '0' + product;
            result[i + j + 1] = temp % 10 + '0';
            carry = temp / 10;
        }

        // 处理最后的进位
        result[i] += carry;
    }

    // 删除结果中的前导零
    int pos = result.find_first_not_of('0');
    if (pos != string::npos) {
        return result.substr(pos);
    }

    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

（2）向量形式

//输入{1,2,3}和{4,5,6}，表示求数123*456的结果值
//输出{5,6,0,8,8}
vector<int> high_mul(vector<int> a, vector<int> b) {  
    int n = a.size(), m = b.size();  
    vector<int> c(n + m, 0); // 初始化结果数组c  
  
    for (int i = n - 1; i >= 0; i--) { // 从右往左遍历a数组  
        int carry = 0; // 进位值  
        for (int j = m - 1; j >= 0; j--) { // 从右往左遍历b数组  
            int temp = c[i + j + 1] + a[i] * b[j] + carry; // 乘积+之前进位  
            
            carry = temp / 10; // 更新进位值  
            c[i + j + 1] = temp % 10; // 更新当前位置的值  
        }  
        c[i] += carry; // 处理最后的进位  
    }  
  
    // 去除结果数组前导0  
    while (c.size() > 1 && c.front() == 0) {  
        c.erase(c.begin());  
    }  
  
    return c;  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

y总给出的模板，

//A是大数，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 = t + A[i] * b;
        }
        C.emplace_back(t % 10);
        t /= 10;
    }
    
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    
    return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20