| 记录编号 |
164803 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
增强的除法问题 |
最终得分 |
100 |
| 用户昵称 |
 Truth.Cirno |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.003 s |
| 提交时间 |
2015-06-06 12:53:50 |
内存使用 |
0.31 MiB |
显示代码纯文本
#include <iostream>
#include <fstream>
#include <cstdio>
#include <string>
using namespace std;
const int MAXLEN=300;
class Bint
{
private:
int len,num[MAXLEN];//length and every number
bool naga;//nagative(true) or not(false)
public:
Bint(void);//way to init
Bint(const string&);//way to init
void set(const string&);//way to set
int getlen(void);//way to get
bool isnaga(void);//way to get
string tostring(void);//way to get
//friends
friend int bcmp(const Bint&,const Bint&);
friend Bint operator+(const Bint&,const Bint&);
friend Bint operator-(const Bint&,const Bint&);
friend Bint operator*(const Bint&,const Bint&);
friend Bint operator/(const Bint&,const Bint&);
};
//assisting
bool istoolong(const string&);//assisting "set" operation
istream& operator>>(istream&,Bint&);//"cin>>bint" Overload
ostream& operator<<(ostream&,Bint);//"cout<<bint" Overload
//friends
int bcmp(const Bint&,const Bint&);//(-1: abs(a) larger)(0 abs value equal)(1: abs(b) larger)
Bint operator+(const Bint&,const Bint&);//"bint+bint" Overload
Bint operator-(const Bint&,const Bint&);//"bint-bint" Overload
Bint operator*(const Bint&,const Bint&);//"bint*bint" Overload
Bint operator/(const Bint&,const Bint&);//"bint/bint" Overload
int main(void)
{
freopen("div.in","r",stdin);
freopen("div.out","w",stdout);
Bint a,b;
cin>>a>>b;
cout<<a/b<<endl;
return(0);
}
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<members>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
Bint::Bint(void)
{
int i;
for (i=0;i<MAXLEN;i++)
num[i]=0;
len=0;
naga=false;
}
Bint::Bint(const string& str)
{
set(str);
}
void Bint::set(const string& str)
{
int i;
//exception
if (istoolong(str))
{
cout<<"\nError when setting Bint: number too large.\n";
cout<<"Now set the Bint with \"0\".\n";
set("0");
return;
}
//non-exception
for (i=0;i<MAXLEN;i++)
num[i]=0;
if (str[0]=='-')
{
len=str.length()-1;
naga=true;
}
else
{
len=str.length();
naga=false;
}
for (i=0;i<len;i++)
num[i]=str[str.length()-1-i]-'0';
}
int Bint::getlen(void)
{
return(len);
}
bool Bint::isnaga(void)
{
return(naga);
}
string Bint::tostring(void)
{
if (len==0||(len==1&&num[0]==0))
return("0");
string str="";
int i;
if (naga)
str+='-';
for (i=len-1;i>=0;i--)
str+=char(num[i]+'0');
return(str);
}
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<assisting>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
bool istoolong(const string& str)
{
if (str[0]!='-'&&int(str.length())>MAXLEN)
return(true);
if (str[0]=='-'&&int(str.length())-1>MAXLEN)
return(true);
return(false);
}
//"cin>>bint" Overload
istream& operator>>(istream& cin,Bint& a)
{
string str="";
cin>>str;
a.set(str);
return(cin);
}
//"cout<<bint" Overload
ostream& operator<<(ostream& cout,Bint a)
{
cout<<a.tostring();
return(cout);
}
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<friends>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//(-1: abs(a) larger)(0 abs value equal)(1: abs(b) larger)
int bcmp(const Bint& a,const Bint& b)
{
if (a.len>b.len)
return(-1);
else if (a.len<b.len)
return(1);
else
{
int i;
for (i=a.len-1;i>=0;i--)
if (a.num[i]>b.num[i])
return(-1);
else if (a.num[i]<b.num[i])
return(1);
}
return(0);
}
//"+" Overload
Bint operator+(const Bint& a,const Bint& b)
{
int i,jin=0;
Bint c;
//deal with nagative number
if (a.naga&&!b.naga)
{
c=a;
c.naga=false;
return(b-c);
}
if (!a.naga&&b.naga)
{
c=b;
c.naga=false;
return(a-c);
}
if (a.naga&&b.naga)
c.naga=true;
//deal with length
c.len=a.len;
if (bcmp(a,b)==1)
c.len=b.len;
//a plus b
for (i=0;i<c.len;i++)
c.num[i]=a.num[i]+b.num[i];
//deal with number larger than 10
jin=0;
for (i=0;i<c.len;i++)
{
c.num[i]+=jin;
jin=c.num[i]/10;
c.num[i]%=10;
}
//deal with final length
if (jin)
{
c.num[c.len]=jin;
c.len++;
}
return(c);
}
//"-" Overload
Bint operator-(const Bint& a,const Bint& b)
{
int i,jie=0;
Bint c;
//deal with nagative number (phase 1)
if (a.naga&&!b.naga)//(-a)-(b)=(-a)+(-b)
{
c=b;
c.naga=true;
return(a+c);
}
if (!a.naga&&b.naga)//(a)-(-b)=(a)+(b)
{
c=b;
c.naga=false;
return(a+c);
}
if (a.naga&&b.naga)//(-a)-(-b)=b-a;
{
Bint d;
c=a;
d=b;
c.naga=false;
d.naga=false;
return(d-c);
}
//deal with nagative number (phase 2, last)
if (bcmp(a,b)==1)//(+a)-(+b), but b>a
{
c=b-a;
c.naga=true;
return(c);
}
if (bcmp(a,b)==0)//(+a)-(+b), but b==a
{
c.set("0");
return(c);
}//now, there must be (+a)-(+b), and a>b
//a minus b
c.len=a.len;
for (i=0;i<c.len;i++)
c.num[i]=a.num[i]-b.num[i];
//deal with number smaller than 0
jie=0;
for (i=0;i<c.len;i++)
{
c.num[i]-=jie;
if (c.num[i]<0)
{
jie=1;
c.num[i]+=10;
}
else
jie=0;
}
//deal with final length
//(find the first nonzero-number)
for (i=c.len-1;i>=1;i--)
if (c.num[i]!=0)
break;
c.len=i+1;
return(c);
}
//"*" Overload
Bint operator*(const Bint& a,const Bint& b)
{
int i,j,jin;
Bint c;
//deal with 0
if ((a.len==1&&a.num[0]==0)||(b.len==1&&b.num[0]==0))
{
c.set("0");
return(c);
}
//deal with nagative number
if ((a.naga&&!b.naga)&&(!a.naga&&b.naga))
c.naga=true;
//deal with length
c.len=a.len+b.len-1;
//a times b
for (i=0;i<a.len;i++)
for (j=0;j<b.len;j++)
c.num[i+j]+=a.num[i]*b.num[j];
//deal with number larger than 10
jin=0;
for (i=0;i<=c.len;i++)
{
c.num[i]+=jin;
jin=c.num[i]/10;
c.num[i]%=10;
}
//deal with final length
if (c.num[c.len])
c.len++;
return(c);
}
//"/" Overload
Bint operator/(const Bint& a_origin,const Bint& b_origin)
{
int i,len;
Bint c,a=a_origin,b=b_origin;
//exception
if (b.len==1&&b.num[0]==0)
{
cout<<"\nError when operating \"a/b\": a/b and b is 0.\n";
cout<<"Now set the result as \"0\".\n";
c.set("0");
return(c);
}
if (a.len==1&&a.num[0]==0)
{
c.set("0");
return(c);
}
if (bcmp(a,b)==1)
{
c.set("0");
return(c);
}
//deal with nagative number
if ((a.naga&&!b.naga)&&(!a.naga&&b.naga))
c.naga=true;
//enlarge (b) for operation (a-b) in (a/b)
//(b????,???a????)
len=a.len-b.len;
c.len=len;
for (i=b.len-1;i>=0;i--)//target size is (a), copy numbers of (b) for enlarge
b.num[i+len]=b.num[i];
for (i=0;i<len;i++)//and then enlarge (b) with 0
b.num[i]=0;
b.len=a.len;//and now the size of (a) equals size of (b)
//a div b, which perform as (a-b) in loop
/* these comments show the performace afterwards
while (b.len>=b_origin.len)
{
while (a>=b)
{
a-=b;
c+=10^n;//(n) can be got by size of (b)
}
b/=10;
}*/
while (len!=-1)
{
while (bcmp(a,b)!=1)
{
a=a-b;
c.num[len]++;
}
len--;
//to make (b) a little smaller (b/=10)
b.len--;
if (len!=-1)
for (i=len;i<b.len;i++)
b.num[i]=b.num[i+1];
b.num[b.len]=0;
}
//deal with final length
for (i=c.len;i>=1;i--)
if (c.num[i]!=0)
break;
c.len=i+1;
return(c);
}