GESP C++
5级
练习题
luogu-P1303 A*B Problem

luogu-P1303 A*B Problem

GESP C++ 五级练习题，高精度计算考点应用。四、五级考生推荐练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。

luogu-P1303 A*B Problem

题目要求

题目背景

高精度乘法模板题。

题目描述

给出两个非负整数，求它们的乘积。

输入格式

输入共两行，每行一个非负整数。

输出格式

输出一个非负整数表示乘积。

输入输出样例 #1

输入 #1 
1 
2
输出 #1 
2

说明/提示

每个非负整数不超过 10200010^{2000}。

题目分析

这道题的核心考点是 “高精度计算”，具体来说是 “高精度乘法”。

1. 为什么需要高精度计算？

题目中给出的两个非负整数，每个数的长度最大可能达到 10200010^{2000}（即 2000 位数字）。这远远超出了 C++ 中内置的基础数据类型（如 long long 或 unsigned long long，最大仅能表示 19/20 位数字左右）所能存储的极限范围。因此，我们必须借助数组和字符串来模拟我们小学阶段学习的手算乘法过程。

2. 字符串的读取与逆序存储

为了读取超长整数，我们需要使用 std::string 类型来接收输入的由数字组成的字符串。在拿到字符串形式的数字后，需要将它们逐位转换成整型数字并存入数组 a 和 b 中。 这里有一个很关键的逻辑技巧：逆序存储。我们将数字的个位存入数组的第一个位置（索引为 00），十位存入按索引 11，百位存入索引 22，以此类推。 这样处理的好处在于，当我们在稍后计算相乘产生向上进位时，可以顺应数组下标递增的方向（即高位索引方向）去进行 +1，从而避开了由于长度延伸而引起的繁琐的整体向右平移操作。

3. 核心算法：模拟竖式乘法

高精度乘法的核心逻辑无非是双重循环来模拟竖式乘法： 让数字 AA 中的每一位 a[i] 去乘以数字 BB 中的每一位 b[j]，乘积的结果应该累加到最终结果数组所在的第 i+ji + j 位上：c[i + j] += a[i] * b[j]。

需要注意的是，经过上述计算后，此时数组 c 里的每一个元素可能都会大于 99。在这个阶段，我们先不去处理进位，只是单纯进行对应位上的累加。等所有乘法过程结束后，再统一进行一次整体的向上进位即可。

4. 统一进位与前导零处理

乘法双重循环跑完之后，我们必须顺次遍历结果数组一轮以处理所有进位：

  1. 统一的高位进位：对于结果数组的每一位 c[i]，利用逢十进一的原则，将它对 1010 取整 (c[i] / 10) 累加到它的高一位 c[i + 1] 上，并将当前位自身进行对 1010 取模 (c[i] % 10) 计算并保留余数。
  2. 处理前导零的剔除：两个数（分别有 nn 位和 mm 位）相乘，积的总位数最大也就是 n+mn + m 位（比如 99×99=980199 \times 99 = 9801 就是 4 位）。因此最终结果数组 c 的最大索引位置必定在一个有界的长度内。然而真实的积总位数长度可能并不会达到 n+mn + m 这么大，在结果的最高位往往会产生一些冗余的零（即“前导零”）。我们需要从可能的最大高位开始向下挨个检查，若遇到 0 则将其削去，直到最高有效位（且要注意一种特例：如果是计算结果数字本身为 0 时，至少需保留一位输出，不能把所有 0 都给削空了）。

最后，因为真实的答案数值顺序是反过来的（存放在结果数组里是个位保存在索引 00），所以在拼接输出时，只需按照从大到小的下标顺位依次遍历并将其转换为对应的字符拼接即可。

示例代码 

#include <algorithm>
#include <iostream>

// 数组大小开到 10^6 + 5，题目要求乘数不超过 10^2000，数组足够大
const int N = 10e5 + 5;
// a 数组存放被乘数，b 数组存放乘数，c 数组存放乘积
int a[N], b[N], c[N];

// 高精度乘法函数，传入两个大整数字符串，返回它们的乘积字符串
std::string big_multi(std::string num1, std::string num2) {
    std::string res = "";
    int n = num1.size(), m = num2.size();

    // 逆序将字符串 num1 的每一位数字存入数组 a
    // 使得字符串末尾（个位）存放在 a[0]，十位存放在 a[1]，以此类推
    for (int i = n - 1; i >= 0; i--) {
        a[n - i - 1] = num1[i] - '0';
    }
    // 逆序将字符串 num2 的每一位数字存入数组 b，个位数对应 b[0]
    for (int i = m - 1; i >= 0; i--) {
        b[m - i - 1] = num2[i] - '0';
    }

    // 模拟竖式乘法运算的核心过程
    // a 的第 i 位乘以 b 的第 j 位，乘积应该累加到 c 的第 i+j 位上
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            c[i + j] += a[i] * b[j];
        }
    }

    // 两个数相乘，乘积的总位数最多为它们的位数之和 (n + m)
    int len = n + m;
    // 处理统一进位：遍历乘积数组 c，如果当前位满 10，则向高位进位
    for (int i = 0; i < len; i++) {
        if (c[i] >= 10) {
            c[i + 1] += c[i] / 10;  // 向前（高位）进位
            c[i] %= 10;             // 当前位保留余数（个数）
        }
    }

    // 去除前导零：结果可能没有达到 n + m 位，除了数字 0
    // 本身（至少保留一位），把最高位多余的 0 去掉
    while (len > 1 && c[len - 1] == 0) {
        len--;
    }

    // 从高位到低位，将计算完毕整数逆序拼接回字符串
    for (int i = len - 1; i >= 0; i--) {
        res += c[i] + '0';
    }

    return res;
}

int main() {
    std::string a, b;
    // 读入两个非常大的非负整数字符串
    std::cin >> a >> b;
    // 调用大整数乘法计算函数并输出结果
    std::cout << big_multi(a, b) << std::endl;
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于
luogu-P1163 银行贷款