思路
高精度除法要求求出商和余数,那我们的思路就是:把上一次的余数乘10,再加上当前位上的数,就是被除数,后面往C(答案)里压入这个数字除以b,就可以得到商在这个位置上的数字。
- 从高到低运算
- 注意去掉前导零
- 由于在除法运算中,高位到低位运算,因此C的前导零都在vector的前面而不是尾部,vector只有删除最后一个数字pop_back是常数复杂度,而对于删除第一位没有相应的库函数可以使用,而且删除第一位,其余位也要前移,因此我们将C翻转,这样0就位于数组尾部,可以使用pop函数删除前导0
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int> &A,int b,int &r)
{
vector<int> C;
for(int i=A.size()-1;i>=0;i--)//对A从最高位开始处理
{
r=r*10+A[i];//将上次的余数*10在加上当前位的数字,便是该位需要除的被除数
C.push_back(r/b);//所得即为商在这一位的数字
r%=b;
}
reverse(C.begin(),C.end());//反转C,使begin是低位,end是高位,目的是去掉前导零
while(C.size()>1&&C.back()==0) C.pop_back();//去掉前导零
return C;
}
int main()
{
vector<int> A;
string a;
int b;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
int r=0;//余数
auto C=div(A,b,r);//begin是低位,end是高位
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
puts("");
printf("%d",r);
return 0;
}