AcWing 794. 高精度除法
原题链接
简单
作者:
王烽
,
2022-09-23 22:44:59
,
所有人可见
,
阅读 116
相较于其他高精度问题的区别
加减乘都是从个位开始,但是除法是从最高位开始,得到的结果在数组中也是先高位
这导致前导0出现在了数组前(而非常规的数组末尾)所以要先reverse
对所有高精度运算中t作用的概括
一开始t作为和待运算单位同等地位的身份参与运算
随后t要更新如加减乘的“%b”,除中的“*10”使得其地位与下一次迭代参与运算的数字相同
C++ 代码(WA)
#include<iostream>
#include<vector>
using namespace std;
vector<int> div(vector<int> &A,int b){
vector<int> C;
int t=0;
for(int i=A.size()-1;i>=0;i--){
t=(A[i]+10*t)/b;
C.push_back((A[i]+10*t)/b);
}
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');
auto C=div(A,b);
for(int i=C.size()-1;i>=0;i--)cout<<C[i];
return 0;
}
//WA的原因,对于t的错误利用(先迭代再使用是错的)
C++代码(AC)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int> &A,int b,int &t){
vector<int> C;
t=0;
for(int i=A.size()-1;i>=0;i--){
t=10*t+A[i];
C.push_back(t/b);
t%=b; //照理来说这里应该乘以10完成彻底的地位上升,但是考虑到最后有余数,在用的时候再升地位
}
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 t;
auto C=div(A,b,t);
for(int i=C.size()-1;i>=0;i--)cout<<C[i];
cout<<endl<<t<<endl;
return 0;
}