AcWing 794. 高精度除法
原题链接
简单
作者:
lemon_242
,
2024-02-26 15:08:18
,
所有人可见
,
阅读 19
y总原样模板+注释理解
#include <iostream>
#include <vector>
#include <algorithm> //这是为了使用reverse()函数
using namespace std;
//高精度除法,A / b,商是C,余数是r
vector<int> div(vector<int> &A, int b, int &r) //通过引用把余数r的值传回去
{
vector<int> C; //C数组记录商的结果
r = 0; //r表示余数,同时也在后续运算中充当每一步除法的被除数,一开始设置为0
for (int i = A.size() - 1; i >= 0; i -- ) //同样从A数组的尾巴开始,代表高位
{
// “=”右边的r代表 前一位 除法运算后得到的余数,这个余数需要*10然后加本位A[i],得到本次运算的被除数
//相当于 前一位除法运算后得到的余数是1,本位A[i]是2,那么1*10+2=12,12就是本次运算的被除数
r = r * 10 + A[i];
C.push_back(r / b); //被除数 整除 除数(b)得到商,放入结果数组C中
r %= b; //被除数 模 除数(b)得到本次运算的余数r
}
//因为上面这种操作先计算出来的是商的高位数字,不像加法,减法,乘法先计算出来的是低位数字
//由于除法的运算性质,计算得到的商的存储不符合“倒序”存储,和之前的3种运算不统一
//所以需要把数组C整个逆序,使用函数reverse
reverse(C.begin(), C.end());
//逆序存储的数组C 此时也可以用同样的方法去掉前导0
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
vector<int> A;
int B;
cin >> a >> B;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
int r;
auto C = div(A, B, r);
//数组C逆序过了,所以还是逆序输出
for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
cout << endl << r << endl;
return 0;
}