AcWing 793. 高精度乘法

[toc]

第一讲 基础算法 - 04高精度 | Akari的小站

AcWing 793. 高精度乘法【简单】

1 题目描述

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

输入格式:
共两行，第一行包含整数 A，第二行包含整数 B。

输出格式:
共一行，包含 A×B 的值。

数据范围:
1 ≤ A 的长度 ≤ 100000,
0 ≤ B ≤ 10000

输入样例：

2
3

输出样例：

6

2 算法步骤

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

3 时间复杂度

时间复杂度: O(n^2)

4 AC代码

注意 : lc = la + lb, 结合图片去理解.

4.1 数组

#include <bits/stdc++.h>
using namespace std;

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)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    string a, b;
    cin >> a >> b;
    la = a.size(), lb = b.size(), lc = la + lb;     // 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 时）
}

4.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());
}
#include <bits/stdc++.h>
using namespace std;

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());      // lc = la + lb
    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时）
}