【例1.3】高精度乘法

题目描述

输入两个高精度正整数 $M$ 、 $N$ （均小于 100 位），输出 $M \times N$ 。两行各一整数。样例：输入 36 3，输出 108。

思路

把 $M$ 、 $N$ 逆序拆到 int 数组（下标 1 是最低位），双重循环把每位乘积累加到 c[i+j-1]，再从低位到高位统一进位，最后倒序输出。整体 $O(pq)$ ， $p$ 、 $q$ 都百位以内，轻松通过。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 04:18
# update_at: 2026-09-30 04:27

import sys


def solve() -> None:
    """读入两个高精度正整数，输出它们的积。"""
    # 两个操作数各占一行；split() 按空白切分，恰好得到两个 token
    m, n = sys.stdin.buffer.read().split()
    # int 是任意精度整数：竖式相乘和进位由解释器完成，100 位量级用 O(len(m)*len(n)) 的竖式
    print(int(m) * int(n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:49
 * update_at: 2026-10-05 08:49
 */
// main.cpp：高精度乘法。两个不超过 100 位的十进制正整数 M、N，求 M*N。

#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

const int MAXN = 205; // 两个 100 位数相乘，结果最多 200 位

// 全局位数组：a[1..la] 存 M 的逆序低位在前数字，b[1..lb] 存 N 的逆序低位在前数字，c[1..lc] 存积的逆序低位在前数字
int a[MAXN];
int b[MAXN];
int c[MAXN];

int la, lb, lc; // M、N、积的位数

void mul() {
    // 双重循环：第 i 位 × 第 j 位累加到第 i+j-1 位
    for (int i = 1; i <= la; ++i) {
        for (int j = 1; j <= lb; ++j) {
            c[i + j - 1] += a[i] * b[j];
        }
    }

    // 从低位到高位统一进位
    lc = la + lb;
    for (int i = 1; i <= lc; ++i) {
        if (c[i] >= 10) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    }

    // 去掉前导零：lc 可能比真实位数多 1（最高位刚好为 0 的情况）
    while (lc > 1 && c[lc] == 0) {
        --lc;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string M, N;
    cin >> M >> N;

    la = (int)M.size();
    lb = (int)N.size();

    // 逆序写入：a[1] = M 的最低位
    for (int i = 0; i < la; ++i) {
        a[i + 1] = M[la - 1 - i] - '0';
    }
    for (int i = 0; i < lb; ++i) {
        b[i + 1] = N[lb - 1 - i] - '0';
    }

    mul();

    // 倒序输出
    for (int i = lc; i >= 1; --i) {
        cout << c[i];
    }
    cout << '\n';

    return 0;
}

【例1.3】高精度乘法

目录

题目描述

思路

参考代码