高精度乘低精度
515 字
3 分钟
高精度乘低精度

高精度乘低精度
高精度乘低精度指的是:
一个很大的整数 A 乘以一个普通整数 b比如:
123456789123456789 * 7大整数 A 用字符串读入,小整数 b 可以用 int 存。
1、核心思想
仍然是模拟竖式。
从个位开始,每一位都乘以 b,再加上上一位传来的进位。
例如:
123 * 4倒序看:
3 * 4 = 12,当前位 2,进位 12 * 4 + 1 = 9,当前位 9,进位 01 * 4 = 4,当前位 4结果是:
4922、为什么循环条件里要有 t
模板里常见这一句:
for (int i = 0; i < A.size() || t; i++)意思是:即使所有位都处理完了,只要还有进位,就继续处理。
比如:
999 * 9最后会多出高位进位。
3、C++ 模板
#include <bits/stdc++.h>using namespace std;
vector<int> mul(vector<int>& A, int b) { vector<int> C;
int t = 0; for (int i = 0; i < (int)A.size() || t; i++) { if (i < (int)A.size()) t += A[i] * b;
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'); }
vector<int> C = mul(A, b);
for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
return 0;}4、处理乘以 0
如果 b = 0,循环仍然能得到结果 0。
因为 C 最后会保留一个数字,不会被前导零清理删空:
while (C.size() > 1 && C.back() == 0) C.pop_back();5、容易写错的地方
(1)string 不要写成 sting
string a;拼写错误会直接编译失败。
(2)字符要减 '0'
A.push_back(a[i] - '0');不能直接存 a[i]。
(3)函数调用后要加分号
vector<int> C = mul(A, b);(4)输出的是 C[i]
printf("%d", C[i]);不是输出整个 vector。
6、复杂度
如果大整数有 n 位,那么每一位处理一次:
时间复杂度 O(n)空间复杂度 O(n)总结
高精度乘低精度记住一句话:
当前位 = A[i] * b + 进位然后取个位放入答案,把十位以上继续作为进位。
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!














