当前位置：首页 > news >正文

【算法】【高精度】acwing算法基础 793. 高精度乘法

news 2025/6/29 0:30:21

题目

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

输入格式

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

输出格式

共一行，包含 A×B 的值。

数据范围

1≤A的长度≤100000, 0≤B≤10000

输入样例： 2

3

输出样例：

6

来源：acwing算法基础 793. 高精度乘法

思路（注意事项）

去掉结果中的前导零:while (C.size() > 1 && C.back() == 0) C.pop_back();
注意函数mul()，循环条件中的t。

纯代码

#include<bits/stdc++.h>
using namespace std;vector<int> mul(vector<int> A, int b)
{int t = 0;vector<int> C;for (int i = 0; i < A.size() || t; i ++){if (i < A.size()) t += b * A[i];C.push_back(t % 10);t /= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}
int main()
{string a;int b;cin >> a >> b;vector<int> A;for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');auto C = mul (A, b);for (int i = C.size() - 1; i >= 0; i --) cout << C[i];return 0; 
}

题解（带注释）

#include<bits/stdc++.h>
using namespace std;// 高精度乘法函数：计算一个大整数 A 和一个整数 b 的乘积
vector<int> mul(vector<int> A, int b) {int t = 0; // 进位标志vector<int> C; // 存储结果的数组// 逐位计算乘法for (int i = 0; i < A.size() || t; i++) {if (i < A.size()) t += b * A[i]; // 如果 A 还有位数，计算当前位的乘积并加上进位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;    // 存储输入的整数cin >> a >> b; // 输入大整数和整数vector<int> A; // 存储大整数的每一位（逆序存储）for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); // 将字符串逆序转换为数字数组auto C = mul(A, b); // 调用高精度乘法函数计算结果// 输出结果（逆序输出，恢复原始顺序）for (int i = C.size() - 1; i >= 0; i--) cout << C[i];return 0;
}