高精度乘低精度

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

高精度乘低精度#

高精度乘低精度指的是:

一个很大的整数 A 乘以一个普通整数 b

比如:

123456789123456789 * 7

大整数 A 用字符串读入,小整数 b 可以用 int 存。

1、核心思想#

仍然是模拟竖式。

从个位开始,每一位都乘以 b,再加上上一位传来的进位。

例如:

123 * 4

倒序看:

3 * 4 = 12,当前位 2,进位 1
2 * 4 + 1 = 9,当前位 9,进位 0
1 * 4 = 4,当前位 4

结果是:

492

2、为什么循环条件里要有 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 + 进位

然后取个位放入答案,把十位以上继续作为进位。

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

高精度乘低精度
https://blog.tjcheng.cn/posts/migrated/old-86/
作者
TengJinCheng
发布于
2025-10-09
许可协议
CC BY-NC-SA 4.0
Profile Image of the Author
TengJinCheng
Hello, I'm Teng.
公告
欢迎来到TengJinCheng工作铺!
音乐
封面

音乐

暂未播放

0:000:00
暂无歌词
分类
标签
站点统计
文章
157
分类
7
标签
114
总字数
109,939
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
Local
博客版本
Firefly v6.13.4
文章许可
CC BY-NC-SA 4.0

文章目录