高精度乘法

一、算法思想

使用数组来存储大整数，为了方便处理进位，可以按照由低位到高位的顺序存储。

注意

该模板仅考虑高精度与低精度相乘的情况。

定义高精度整数 $A$，低精度整数 $b$，以及低位对当前位的进位 $t$。

由于 $b$ 的位数少，因此可以将 $b$ 看作一个整体，即：转换成 $b \times A$ 后再模拟手算乘法。

二、算法模板

C++

// 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 += b * A[i];
        C.push_back(t % 10);
        t /= 10;
    }
    
    // 去除前导 0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

Go

func mul(A []int, b int) (C []int) {
    t := 0
    for i := 0; i < len(A) || t > 0; i++ {
        if i < len(A) {
            t += A[i] * b
        }
        C = append(C, t%10)
        t /= 10
    }
    // 去除前导 0
    for len(C) > 1 && C[len(C)-1] == 0 {
        C = C[:len(C)-1]
    }
    return
}

三、代码实战

AcWing 0793

---

题目：高精度乘法

给定两个非负整数（不含前导 $0$）$A$ 和 $B$，请你计算 $A \times B$ 的值。

输入格式

共两行，第一行包含整数 $A$，第二行包含整数 $B$。

输出格式

共一行，包含 $A \times B$ 的值。

数据范围

$1\le \text{A 的长度} \le 10^5$

$0\le \text{B} \le 10^4$

输入样例：

2

3

输出样例：

6

解答代码：

#include <iostream>
#include <vector>

using namespace std;

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 += b * A[i];
        C.push_back(t % 10);
        t /= 10;
    }
    
    // 去除前导 0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main()
{
    string a;
    int b;
    vector<int> A;
    
    cin >> a >> b;
    for (int i = a.length() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    
    vector<int> C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    
    return 0;
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

// 高精度乘法
// // C = A * b，满足 A >= 0, b >= 0
func mul(A []int, b int) (C []int) {
    t := 0
    for i := 0; i < len(A) || t > 0; i++ {
        if i < len(A) {
            t += A[i] * b
        }
        C = append(C, t%10)
        t /= 10
    }
    // 去除前导 0
    for len(C) > 1 && C[len(C)-1] == 0 {
        C = C[:len(C)-1]
    }
    return
}

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var a string
    var b int
    Fscan(in, &a, &b)

    var A []int
    for i := len(a) - 1; i >= 0; i-- {
        A = append(A, int(a[i]-'0'))
    }

    C := mul(A, b)
    for i := len(C) - 1; i >= 0; i-- {
        Fprintf(out, "%d", C[i])
    }
}

func main() {
    run(os.Stdin, os.Stdout)
}