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

高精度除低精度
高精度除低精度指的是:
一个很大的整数 A 除以一个普通整数 b例如:
123456789123456789 / 7大整数用字符串读入,小整数 b 用 int 存。
1、核心思想
除法和加减乘不同,它更适合从高位往低位处理。
手算除法时也是从最高位开始:
当前余数 r 先乘 10,再加上当前位当前商位 = r / b新的余数 = r % b2、为什么输入仍然倒序存储
为了和高精度加减乘保持一致,我们仍然把数字倒序存入 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,余数 1r = 1 * 10 + 2 = 12,商位 2,余数 2r = 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它本质上就是把手算竖式除法翻译成代码。
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!














