基础算法(8) —— 高精度除法模板

96 阅读 0 评论 64 点赞

我是靠谱客的博主懦弱麦片，这篇文章主要介绍基础算法(8) —— 高精度除法模板，现在分享给大家，希望可以做个参考。

高精度除法

给定两个非负整数A，B，请你计算 A / B的商和余数。

输入格式
共两行，第一行包含整数A，第二行包含整数B。

输出格式
共两行，第一行输出所求的商，第二行输出所求余数。

数据范围
$1 \leq A 的长度 \leq 100000,$
$1 \leq B \leq 10000$
$B 一定不为 0$

输入样例：

复制代码

输出样例：

复制代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
e#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>

using namespace std;
//C = A / b;商是C，余数是r 
vector<int> div(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());
	
	//删除前导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');
    int r;
    vector<int> C = div(A, b, r);
    for(int i = C.size() - 1;i >= 0;i--)
        printf("%d", C[i]);
    printf("%d", r);
    return 0;
}