free 高精乘、加、减
zengyige7760 · · 个人记录
class Bigint{
public:
int a[105];
Bigint()
{
memset(a,0,sizeof(a));
a[0]=1;
}
friend ostream & operator << (ostream &o,const Bigint &b);
friend istream & operator >> (istream &in,Bigint &b);
Bigint operator + (Bigint r)
{
Bigint c;
c.a[0]=max(a[0],r.a[0]);
for(int i=1;i<=c.a[0];i++)
{
c.a[i]+=a[i]+r.a[i];
c.a[i+1]+=c.a[i]/10;
c.a[i]%=10;
}
if(c.a[c.a[0]+1])
c.a[0]++;
while(c.a[c.a[0]]==0&&c.a[0]>=2)
c.a[0]--;
return c;
}
Bigint operator - (Bigint r)
{
Bigint c;
c.a[0]=max(a[0],r.a[0]);
for(int i=1;i<=c.a[0];i++)
{
c.a[i]+=a[i]-r.a[i];
if(c.a[i]<0)
{
c.a[i]+=10;
c.a[i+1]--;
}
}
while(c.a[c.a[0]]==0&&c.a[0]>=2)
c.a[0]--;
return c;
}
Bigint operator * (Bigint r)
{
Bigint c;
c.a[0]=a[0]+r.a[0];
for(int i=1;i<=a[0];i++)
for(int j=1;j<=r.a[0];j++)
{
c.a[i+j-1]+=a[i]*r.a[j];
}
for(int i=1;i<=c.a[0];i++)
{
c.a[i+1]+=c.a[i]/10;
c.a[i]%=10;
}
while(c.a[c.a[0]]==0&&c.a[0]>=2)
c.a[0]--;
return c;
}
bool operator < (Bigint r)
{
if(a[0]!=r.a[0])
return a[0]<r.a[0];
for(int i=a[0];i>=1;i--)
if(a[i]!=r.a[i])
return a[i]<r.a[i];
return false;
}
bool operator > (Bigint r)
{
if(a[0]!=r.a[0])
return a[0]>r.a[0];
for(int i=a[0];i>=1;i--)
if(a[i]!=r.a[i])
return a[i]>r.a[i];
return false;
}
bool operator <= (Bigint r)
{
if(a[0]!=r.a[0])
return a[0]<=r.a[0];
for(int i=a[0];i>=1;i--)
if(a[i]!=r.a[i])
return a[i]<=r.a[i];
return true;
}
bool operator >= (Bigint r)
{
if(a[0]!=r.a[0])
return a[0]>=r.a[0];
for(int i=a[0];i>=1;i--)
if(a[i]!=r.a[i])
return a[i]>=r.a[i];
return true;
}
Bigint operator / (Bigint r)
{
Bigint q,x=*this,y=r,t;
if(x<y)
{
q.a[0]=1;
q.a[1]=0;
return q;
}
q.a[0]=x.a[0]-y.a[0]+1;
for(int i=q.a[0];i>=1;i--)
{
memset(t.a,0,sizeof(t.a));
t.a[0]=y.a[0]+i-1;
for(int j=1;j<=y.a[0];j++)
t.a[j+i-1]=y.a[j];
q.a[i]=0;
while(x>=t)
{
q.a[i]++;
x=x-t;
}
}
while(q.a[q.a[0]]==0&&q.a[0]>=2)
q.a[0]--;
return q;
}
Bigint operator % (Bigint r)
{
Bigint x=*this,y=r,t;
if(x<y)
return x;
int len=x.a[0]-y.a[0]+1;
for(int i=len;i>=1;i--)
{
memset(t.a,0,sizeof(t.a));
t.a[0]=y.a[0]+i-1;
for(int j=1;j<=y.a[0];j++)
t.a[j+i-1]=y.a[j];
while(x>=t)
x=x-t;
}
while(x.a[x.a[0]]==0&&x.a[0]>=2)
x.a[0]--;
return x;
}
};
istream & operator >> (istream &in,Bigint &b)
{
string s;
in>>s;
b.a[0]=s.size();
for(size_t i=0;i<s.size();i++)
b.a[i+1]=s[s.size()-1-i]-'0';
return in;
}
ostream & operator << (ostream &o,const Bigint &b)
{
for(int i=b.a[0];i>=1;i--)
o<<b.a[i];
return o;
}
Bigint int_to_bigint(int num)
{
Bigint res;
if(num==0)
{
res.a[0]=1;
res.a[1]=0;
return res;
}
if(num<0)
{
num=-num;
}
int len=0;
while(num>0)
{
res.a[++len]=num%10;
num/=10;
}
res.a[0]=len;
return res;
}
压行后的：
class Bigint{public:int a[105];Bigint(){memset(a,0,sizeof(a));a[0]=1;}friend ostream & operator << (ostream &o,const Bigint &b);friend istream & operator >> (istream &in,Bigint &b);Bigint operator + (Bigint r){Bigint c;c.a[0]=max(a[0],r.a[0]);for(int i=1;i<=c.a[0];i++){c.a[i]+=a[i]+r.a[i];c.a[i+1]+=c.a[i]/10;c.a[i]%=10;}if(c.a[c.a[0]+1])c.a[0]++;while(c.a[c.a[0]]==0&&c.a[0]>=2)c.a[0]--;return c;}Bigint operator - (Bigint r){Bigint c;c.a[0]=max(a[0],r.a[0]);for(int i=1;i<=c.a[0];i++){c.a[i]+=a[i]-r.a[i];if(c.a[i]<0){c.a[i]+=10;c.a[i+1]--;}}while(c.a[c.a[0]]==0&&c.a[0]>=2)c.a[0]--;return c;}Bigint operator * (Bigint r){Bigint c;c.a[0]=a[0]+r.a[0];for(int i=1;i<=a[0];i++)for(int j=1;j<=r.a[0];j++){c.a[i+j-1]+=a[i]*r.a[j];}for(int i=1;i<=c.a[0];i++){c.a[i+1]+=c.a[i]/10;c.a[i]%=10;}while(c.a[c.a[0]]==0&&c.a[0]>=2)c.a[0]--;return c;}bool operator < (Bigint r){if(a[0]!=r.a[0])return a[0]<r.a[0];for(int i=a[0];i>=1;i--)if(a[i]!=r.a[i])return a[i]<r.a[i];return false;}bool operator > (Bigint r){if(a[0]!=r.a[0])return a[0]>r.a[0];for(int i=a[0];i>=1;i--)if(a[i]!=r.a[i])return a[i]>r.a[i];return false;}bool operator <= (Bigint r){if(a[0]!=r.a[0])return a[0]<=r.a[0];for(int i=a[0];i>=1;i--)if(a[i]!=r.a[i])return a[i]<=r.a[i];return true;}bool operator >= (Bigint r){if(a[0]!=r.a[0])return a[0]>=r.a[0];for(int i=a[0];i>=1;i--)if(a[i]!=r.a[i])return a[i]>=r.a[i];return true;}Bigint operator / (Bigint r){Bigint q,x=*this,y=r,t;if(x<y){q.a[0]=1;q.a[1]=0;return q;}q.a[0]=x.a[0]-y.a[0]+1;for(int i=q.a[0];i>=1;i--){memset(t.a,0,sizeof(t.a));t.a[0]=y.a[0]+i-1;for(int j=1;j<=y.a[0];j++)t.a[j+i-1]=y.a[j];q.a[i]=0;while(x>=t){q.a[i]++;x=x-t;}}while(q.a[q.a[0]]==0&&q.a[0]>=2)q.a[0]--;return q;}Bigint operator % (Bigint r){Bigint x=*this,y=r,t;if(x<y)return x;int len=x.a[0]-y.a[0]+1;for(int i=len;i>=1;i--){memset(t.a,0,sizeof(t.a));t.a[0]=y.a[0]+i-1;for(int j=1;j<=y.a[0];j++)t.a[j+i-1]=y.a[j];while(x>=t)x=x-t;}while(x.a[x.a[0]]==0&&x.a[0]>=2)x.a[0]--;return x;}};istream & operator >> (istream &in,Bigint &b){string s;in>>s;b.a[0]=s.size();for(size_t i=0;i<s.size();i++)b.a[i+1]=s[s.size()-1-i]-'0';return in;}ostream & operator << (ostream &o,const Bigint &b){for(int i=b.a[0];i>=1;i--)o<<b.a[i];return o;}Bigint int_to_bigint(int num){Bigint res;if(num==0){res.a[0]=1;res.a[1]=0;return res;}if(num<0){num=-num;}int len=0;while(num>0){res.a[++len]=num%10;num/=10;}res.a[0]=len;return res;}