AcWing 793. 高精度乘法
原题链接
简单
作者:
lemon_242
,
2024-02-26 14:34:17
,
所有人可见
,
阅读 23
y总原样模板+注释理解
#include <iostream>
#include <vector>
using namespace std;
//高精度乘法
vector<int> mul(vector<int> &A, int b) //vector<int> &A,这里使用引用,减少copy的时间
{
vector<int> C; //存储结果的数组C
int t = 0; //t表示进位,同时t充当每一位上A[i] * b + t得到的结果
for (int i = 0; i < A.size() || t; i ++ ) //当大整数A的位数耗尽 或者 进位t为0【2个判断条件】,乘法结束
{
//可能存在A的位数耗尽,但是进位t不为0,需要往总结果中加入进位t,也就是整个乘法的“最后一步”
//此时不执行t += A[i] * b,只执行C.push_back(t % 10)
//所以外层for循环需要2个判断条件,内层需要 “i < A.size()” 1个判断条件
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10); // t % 10计算的是本位上的数字是多少
t /= 10; // t /= 10计算的是进位的数字是多少
}
//上面这一通操作需要防止123*0 = 000的情况,需要删掉前导0,只留1个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'); //a[i] - '0'把字符转化成数字
auto C = mul(A, b);
for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
return 0;
}