AcWing 794. 高精度除法
原题链接
简单
作者:
yysh
,
2022-11-25 20:37:18
,
所有人可见
,
阅读 162
高精度除法
高精度 / 低精度
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int> & a1, int b, int &t) {
vector<int> c;
//由于我们是倒序存入的数,但是除法需要从高位开始计算,所以,我们倒序循环
for(int i = a1.size() - 1; i >= 0; i--) {
//余数 = 上一次计算的余数 * 10 + 当前位置上的数
t = t * 10 + a1[i];
//存入商
c.push_back(t / b);
//取余除数,更新当前的余数
//如果t >= b,说明t可以除以b,那么我们进行更新,反之,说明t除以不了,那么t不变
t %= b;
}
//除法可能存在前导的0,所以我们需要处理前导的0
//由于我们存入答案数组的结果是顺序存入的,但是vector没办法弹出前面的元素,只能尾部弹出
//所以,我们先反转数组,让高位移动到尾部,然后弹出前导的0
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> a1(a.size(), 0);
//除法本来可以不用倒序存储,但是我们为了保持一致性,选择倒序存入
for(int i = a.size() - 1; i >= 0; i--) {
a1[a.size() - 1 - i] = a[i] - '0';
}
//声明t表示余数
int t = 0;
auto c1 = div(a1, b, t);
//由于我们处理前导的0,所以在答案数组中的数又变成了倒序存储,所以,我们需要倒序输出
for(int i = c1.size() - 1; i >= 0; i--) {
printf("%d", c1[i]);
}
//换行,输出最终的余数
cout << "\n" << t;
return 0;
}