高精度除低精度

617 字
3 分钟
高精度除低精度

高精度除低精度#

高精度除低精度指的是:

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

例如:

123456789123456789 / 7

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

1、核心思想#

除法和加减乘不同,它更适合从高位往低位处理。

手算除法时也是从最高位开始:

当前余数 r 先乘 10,再加上当前位
当前商位 = r / b
新的余数 = r % b

2、为什么输入仍然倒序存储#

为了和高精度加减乘保持一致,我们仍然把数字倒序存入 vector:

12345 -> [5, 4, 3, 2, 1]

但做除法时从高位开始,所以循环从 A.size() - 1 往 0 走。

3、C++ 模板#

#include <bits/stdc++.h>
using namespace std;
vector<int> divide(vector<int>& A, int b, int& r) {
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i--) {
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
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');
}
int r = 0;
vector<int> C = divide(A, b, r);
for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
printf("\n%d\n", r);
return 0;
}

这里输出两行:

第一行:商
第二行:余数

如果题目只要求商,就可以不输出余数。

4、为什么要 reverse#

循环从高位到低位处理,所以 C.push_back 的顺序是从商的高位到低位。

为了和其他高精度模板保持一致,最后把 C 翻转成“低位在前”:

reverse(C.begin(), C.end());

这样输出仍然可以统一使用:

for (int i = C.size() - 1; i >= 0; i--)

5、手推一个例子#

计算:

123 / 5

从高位开始:

r = 1,商位 0,余数 1
r = 1 * 10 + 2 = 12,商位 2,余数 2
r = 2 * 10 + 3 = 23,商位 4,余数 3

商是 024,去掉前导零后是 24,余数是 3。

6、容易写错的地方#

(1)string 不要写成 sting#

string a;

(2)除法不能从低位开始#

竖式除法必须从最高位开始处理。

(3)要去掉商的前导零#

while (C.size() > 1 && C.back() == 0) C.pop_back();

(4)不要忘记函数调用分号#

vector<int> C = divide(A, b, r);

总结#

高精度除低精度可以记成:

从高位到低位:r = r * 10 + 当前位,商位 = r / b,余数 = r % b

它本质上就是把手算竖式除法翻译成代码。

文章分享

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

高精度除低精度
https://blog.tjcheng.cn/posts/migrated/old-87/
作者
TengJinCheng
发布于
2025-10-11
许可协议
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

文章目录