AcWing 794. 高精度除法
原题链接
简单
#include <iostream>
// 因为后面要用到翻转函数 reverse() 所以需要在头文件加入 #include <algorithm>
#include <algorithm>
// 要使用STL(Standard Template Library)标准模板库中 vector ,需要在头文件中加入#include <vector>
#include <vector>
using namespace std;
/*
* 高精度除法的基本过程如下:
* 1、预读:将字符串读入的数据a, 读入可变长数组 A。
* 2、运算:按照小学除法,从最高位开始到最低位开始逐步做除法运算。合理处理余数
* 3、收尾:判断是否有前导零,并处理。
*/
vector<int> div(vector<int> A, int b, int &r)
{
vector<int> C;
// 用来存储余数,函数在读入的使用要加入取地址符号 &r 保证 int main() 也能取到余数。
// 余数初始化为0
r = 0;
// 2、运算:根据我们的习惯,小学除法都是从最高位开始运算的,所以我们这里也是从最高位开始运算。
for (int i = A.size() - 1; i >= 0; i -- )
{
// 将上一个循环的余数 r 先乘以10,因为对于当前位上一位的余数要大10倍。
// 并且加上被除数当前位的数,因为 r 初始化为0,所以读最高位的时候 r * 10 还是0,不必担心。
r = r * 10 + A[i];
// 直接除以除数,整数部分存入数组 C 。
C.push_back(r / b);
// 余数部分保存到 r 方便下一步计算。
r %= b;
}
// 因为数组是由高位到低位进行除法运算并存储到 C 数组的,方便我们去除前导零,也符合我们高精度
// 运算的习惯,翻转整个数组。
reverse(C.begin(), C.end());
// 3、收尾:判断是否有前导零,有的话去除掉。
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
int b, r;
vector<int> A;
// 1、预读:将字符串读入的数据a, 读入可变长数组 A。
getline(cin, a);
scanf("%d", &b);
for (int i = a.size() - 1; i >= 0; i -- )
A.push_back(a[i] - '0');
vector<int> C = div(A, b, r);
for (int i = C.size() - 1; i >= 0; i -- )
printf("%d", C[i]);
printf("\n%d", r);
return 0;
}