#gj003. 高精度乘法

高精度乘法

高精度乘法

题目描述

​ 给定两个非负整数 A 和 B,它们的位数可能超过普通整数类型(如 int 或 long long)的表示范围。请使用高精度乘法(Big Integer Multiplication) 计算 A × B 的值,并输出结果。

算法概念

​ 高精度乘法(大整数乘法)是处理超过基本数据类型表示范围的整数乘法运算的常用方法。其核心思想是模拟手工竖式乘法的过程:将两个大整数按位存储在数组中,用第二个数的每一位依次乘以第一个数的每一位,并将结果累加到对应位置,最后统一处理进位。该方法的时间复杂度为 O(la × lb),其中 la 和 lb 分别为两个数的位数。

算法原理与步骤

  1. 字符串读入:将两个大整数以字符串形式读入,方便处理任意长度的数字。
  2. 逆序存储:将字符串中的数字字符转换为整数,并逆序存入整型数组(数组下标 0 对应个位,下标 1 对应十位,以此类推)。
  3. 逐位相乘累加:用第二个数的每一位 b1[i](从低位到高位)依次乘以第一个数的每一位 a1[j](从低位到高位),并将乘积加到结果数组的对应位置 c1[i+j] 上,同时处理进位。具体做法:
    • 对于每个 i,内层循环 j 从 0 到 la-1,计算 c1[i+j] += a1[j] * b1[i] + 进位 x。
    • 计算新的进位 x = c1[i+j] / 10,并保留当前位 c1[i+j] %= 10。
    • 内层循环结束后,将剩余进位 x 赋给 c1[i+la],并重置 x = 0。
  4. 确定结果位数:最高位可能产生进位,因此结果长度 lc 初始为 la + lb - 1,若 c1[lc] 不为 0,则 lc++。
  5. 逆序输出:从最高位到最低位依次输出结果数组中的数字,即为乘积。

输入格式

​ 第一行一个非负整数 A(可能很大)。

​ 第二行一个非负整数 B(可能很大)。

输出格式

​ 一行,输出 A × B 的结果(不含前导零,除非结果为 0,输出 0)。

输入输出样例

输入输出样例 #1

123
456
56088

输入输出样例 #2

999
999
998001

输入输出样例 #3

0
12345
0

数据规模与约定

  • A 和 B 均为非负整数,长度不超过 1000 位。
  • 结果长度不超过 2000 位。
  • 时间限制:1 秒(高精度乘法 O(la × lb),当 la=lb=1000 时约 10^6 次操作,可通过)
  • 内存限制:256 MB

提示

​ 代码提示:

char a[1005], b[1005];
cin >> a >> b;

int la = strlen(a), lb = strlen(b);
int a1[1005] = {}, b1[1005] = {};

// 将 a 逆序存入 a1
for (int i = 0; i < la; i++) {
    
}
// 将 b 逆序存入 b1
for (int i = 0; i < lb; i++) {
    
}

int c1[2005] = {};
int carry = 0;  // 进位

// 用 b 的每一位乘以 a
for (int i = 0; i < lb; i++) {
    for (int j = 0; j < la; j++) {
       //错位相乘
    }
    // 处理剩余进位
    // TODO: c1[i + la] = carry;
    // TODO: carry = 0;
}

// 确定结果位数
int lc = la + lb - 1;
if (c1[lc] != 0) {
    lc++;
}

// 输出结果
for (int i = lc - 1; i >= 0; i--) {
    cout << c1[i];
}

​ 运用提示:

  • 高精度乘法的核心是“逐位相乘累加并处理进位”,模拟了竖式乘法中每一位相乘后错位相加的过程。
  • 注意结果数组 c1 的大小应为 la + lb + 5,最多为 2000 位。
  • 内层循环中,carry 需要实时更新,且每轮外层循环结束后需将剩余 carry 赋给下一位,并重置 carry 为 0。
  • 去除前导零时,如果结果为 0,lc 会保持为 1(因为 la+lb-1 至少为 1),输出时会输出单个 0。
  • 本模板中直接根据结果最高位是否为 0 来确定 lc,无需额外循环去除前导零(因为乘法结果的最低位一定非零,除非乘数为 0,但乘数为 0 时结果只有 0,最高位就是 0,此时 lc=1,输出 0 正确)。