CodeVS/3118

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
高精度练习之除法	★☆☆☆☆	答案正确	100	2015-2-3 23:45:10	错误的去高位（80）

题意

500位以内的除法。

题解

• 以前做过一题高精度除法，但是保证答案为lld以内，所以可以直接二分。这一题也可以二分做，不同在于除以2没有定义，但是很容易想到按位除以2，处理一下即可。
• 于是四则运算凑齐了^_^不过这里的除法不涉及负数（一步一步的给库加内容的过程可以参照 CodeVS/3116高精度加法、CodeVS/3117高精度乘法、CodeVS/3115高精度减法）。
• 这种做法是除法转化为乘法来做，似乎也有乘法转换为减法的做法，请参见：http://codevs.cn/wiki/solution/?problem_id=3118

代码

3118.cpp代码已折叠 展开折叠内容

#include<iostream> #include<iomanip> #include<algorithm> #include<vector> using namespace std; class largeInt { public: const int size() const { return u.size(); } largeInt() { u.clear(); u.push_back(0); } largeInt(const int &number) { u.clear(); u.push_back(number); carry(); } friend istream& operator >> (istream& os,largeInt &ob) { ob.u.clear(); string original; os>>original; for(int i=original.size()-1,j=0,p=1;i>=0;--i) { j+=(original[i]-'0')*p; p*=10; if((!i) || p==10000) { ob.u.push_back(j); j=0; p=1; } } return os; } friend ostream& operator << (ostream& os,const largeInt &ob) { os<<setw(0)<<setfill('0')<<ob.u[ob.size()-1]; for(int i=ob.size()-2;i>=0;--i) os<<setw(4)<<setfill('0')<<ob.u[i]; return os; } friend const bool operator <(const largeInt &a,const largeInt &b) { if(a.size()==b.size()) { for(int i=a.size()-1;i>=0;--i){ if(a.u[i]!=b.u[i]) return a.u[i]<b.u[i]; } return 0; } return a.size()<b.size(); } friend const largeInt operator +(const largeInt &a,const largeInt &b) { largeInt r; r.u.resize(max(a.size(),b.size())); for(int i=0;i<r.size();++i) { if(i<a.size()) r.u[i]+=a.u[i]; if(i<b.size()) r.u[i]+=b.u[i]; } r.carry(); return r; } friend const largeInt operator *(const largeInt &a,const largeInt &b) { largeInt r; r.u.resize(a.size()+b.size()); for(int i=0;i<a.size();++i) { for(int j=0;j<b.size();++j) { r.u[i+j]+=a.u[i]*b.u[j]; } } r.carry(); return r; } friend const largeInt operator /(const largeInt &a,const largeInt &b) { largeInt left=0,right=a,mid; while(left+1<right) { mid=div(left+right); if(a<mid*b) right=mid; else left=mid; } return left; } friend largeInt div(largeInt a) { for(int i=a.size()-1;i>=0;--i) { if(a.u[i]%2&&i>=1) { a.u[i-1]+=10000; } a.u[i]/=2; // cout<<"{"<<a.u[i]<<"}"; } a.carry(); return a; } private: vector<int> u; void carry() { for(int i=0;i<size();++i) { if(u[i]>=10000) { if(i==size()-1) u.push_back(u[i]/10000); else u[i+1]+=u[i]/10000; u[i]%=10000; } } for(int i=size()-1;i!=0;--i) { if(u[i]==0) { u.pop_back(); }else{ break;//fixed// } } } }; int main() { largeInt a,b; cin>>a>>b; cout<<a/b; }