（以“分类:高精度 ==摘要== {{信息题|高精度练习之除法|http://www.codevs.cn/problem/3118/|1|100|错误的去高位|80|time=2015-2-3 23:45:10}} ==题意...”为内容创建页面） |
小 （→题解： 补充另一种做法） |
||
| 第6行： | 第6行： | ||
==题解== | ==题解== | ||
*以前做过一题高精度除法，但是保证答案为lld以内，所以可以直接二分。这一题也可以二分做，不同在于除以2没有定义，但是很容易想到按位除以2，处理一下即可。 | *以前做过一题高精度除法，但是保证答案为lld以内，所以可以直接二分。这一题也可以二分做，不同在于除以2没有定义，但是很容易想到按位除以2，处理一下即可。 | ||
| − | *于是四则运算凑齐了^_^不过这里的除法不涉及负数（一步一步的给库加内容的过程可以参照 [[CodeVS/ | + | *于是四则运算凑齐了^_^不过这里的除法不涉及负数（一步一步的给库加内容的过程可以参照 [[CodeVS/3116|CodeVS/3116高精度加法]]、[[CodeVS/3117|CodeVS/3117高精度乘法]]、[[CodeVS/3115|CodeVS/3115高精度减法]]）。 |
| + | *这种做法是除法转化为乘法来做，似乎也有乘法转换为减法的做法，请参见：http://codevs.cn/wiki/solution/?problem_id=3118 | ||
| + | |||
==代码== | ==代码== | ||
{{折叠|3118.cpp代码已折叠 | {{折叠|3118.cpp代码已折叠 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 高精度练习之除法 | ★☆☆☆☆ | 答案正确 | 100 | 2015-2-3 23:45:10 | 错误的去高位（80） |
500位以内的除法。
| 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;
}
|
CloudLunar