大数模板
发布时间：2020-12-14 02:15:35 所属栏目：大数据 来源：网络整理
导读：#include iostream??? #include cstring??? using ? namespace ? std;??? ??? ? #define DIGIT?? 4????? //四位隔开,即万进制??? #define DEPTH?? 10000??????? //万进制??? #define MAX???? 251??? //题目最大位数/4，要不大直接设为最大位数也行 typedef ?
#include <iostream>???
#include <cstring>???
using?
namespace?
std;???
????
#define DIGIT?? 4????? //四位隔开,即万进制???
#define DEPTH?? 10000??????? //万进制???
#define MAX???? 251??? //题目最大位数/4，要不大直接设为最大位数也行
typedef?
int?
bignum_t[MAX+1];???
?????
/************************************************************************/???
/* 读取操作数，对操作数进行处理存储在数组里???????????????????????????? */???
/************************************************************************/???
read(bignum_t a,istream&is=cin)???
{???
????
char?
buf[MAX*DIGIT+1],ch ;???
i,j ;???
????
memset
((
void
*)a,
sizeof
(bignum_t));???
????
if
(!(is>>buf))
return?
0 ;???
for
(a[0]=
strlen
(buf),i=a[0]/2-1;i>=0;i--)???
????
ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ;???
(a[0]=(a[0]+DIGIT-1)/DIGIT,j=
(buf);j<a[0]*DIGIT;buf[j++]=
'0'
);???
(i=1;i<=a[0];i++)???
(a[i]=0,j=0;j<DIGIT;j++)???
a[i]=a[i]*10+buf[i*DIGIT-1-j]-
'0'?
;???
(;!a[a[0]]&&a[0]>1;a[0]--);???
1 ;???
}???
?????
void?
write(
const?
bignum_t a,ostream&os=cout)???
{???
(os<<a[i=a[0]],i--;i;i--)???
(j=DEPTH/10;j;j/=10)???
os<<a[i]/j%10 ;???
}???
?????
comp(
bignum_t b)???
{???
i ;???
(a[0]!=b[0])???
a[0]-b[0];???
(i=a[0];i;i--)???
(a[i]!=b[i])???
a[i]-b[i];???
0 ;???
}???
?????
const?
b)???
{???
c[12]=???
{???
????????
1????
}???
;???
(c[1]=b;c[c[0]]>=DEPTH;c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++);???
comp(a,c);???
}???
?????
c,monospace!important; min-height:auto!important; background:none!important">d,monospace!important; min-height:auto!important; background:none!important">bignum_t b)???
{???
(b[0]-a[0]<d&&c)???
1 ;???
(i=b[0];i>d;i--)???
{???
t=t*DEPTH+a[i-d]*c-b[i];???
????????
(t>0)
1 ;???
(t<O)
0 ;???
}???
(i=d;i;i--)???
{???
t=t*DEPTH-b[i];???
1 ;???
0 ;???
}???
t>0 ;???
}???
/************************************************************************/???
/* 大数与大数相加?????????????????????????????????????????????????????? */???
/************************************************************************/???
add(bignum_t a,monospace!important; min-height:auto!important; background:none!important">bignum_t b)???
{???
i ;???
(i=1;i<=b[0];i++)???
((a[i]+=b[i])>=DEPTH)???
a[i]-=DEPTH,a[i+1]++;???
(b[0]>=a[0])???
a[0]=b[0];???
else????
(;a[i]>=DEPTH&&i<a[0];a[i]-=DEPTH,i++,a[i]++);???
a[0]+=(a[a[0]+1]>0);???
}???
/************************************************************************/???
/* 大数与小数相加?????????????????????????????????????????????????????? */???
/************************************************************************/???
b)???
{???
i=1 ;???
(a[1]+=b;a[i]>=DEPTH&&i<a[0];a[i+1]+=a[i]/DEPTH,a[i]%=DEPTH,i++);???
(;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);???
}???
/************************************************************************/???
/* 大数相减(被减数>=减数)?????????????????????????????????????????????? */???
/************************************************************************/???
sub(bignum_t a,monospace!important; min-height:auto!important; background:none!important">bignum_t b)???
{???
i ;???
(i=1;i<=b[0];i++)???
((a[i]-=b[i])<0)???
a[i+1]--,a[i]+=DEPTH ;???
(;a[i]<0;a[i]+=DEPTH,a[i]--);???
(;!a[a[0]]&&a[0]>1;a[0]--);???
}???
/************************************************************************/???
/* 大数减去小数(被减数>=减数)?????????????????????????????????????????? */???
/************************************************************************/???
b)???
{???
i=1 ;???
(a[1]-=b;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);???
(;!a[a[0]]&&a[0]>1;a[0]--);???
}???
?????
bignum_t b,monospace!important; min-height:auto!important; background:none!important">d)???
{???
(i=1+d;i<=O;i++)???
((a[i]-=b[i-d]*c)<0)???
a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH ;???
(;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,i++);???
(;!a[a[0]]&&a[0]>1;a[0]--);???
}???
/************************************************************************/???
/* 大数相乘，读入被乘数a，乘数b，结果保存在c[]????????????????????????? */???
/************************************************************************/???
mul(bignum_t c,monospace!important; min-height:auto!important; background:none!important">bignum_t b)???
{???
*)c,monospace!important; min-height:auto!important; background:none!important">(bignum_t));???
(c[0]=a[0]+b[0]-1,i=1;i<=a[0];i++)???
(j=1;j<=b[0];j++)???
((c[i+j-1]+=a[i]*b[j])>=DEPTH)???
c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH ;???
(c[0]+=(c[c[0]+1]>0);!c[c[0]]&&c[0]>1;c[0]--);???
}???
/************************************************************************/???
/* 大数乘以小数，读入被乘数a，乘数b，结果保存在被乘数?????????????????? */???
/************************************************************************/???
mul(bignum_t a,monospace!important; min-height:auto!important; background:none!important">b)???
{???
i ;???
(a[1]*=b,i=2;i<=a[0];i++)???
{???
a[i]*=b ;???
(a[i-1]>=DEPTH)???
a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH ;???
}???
(;!a[a[0]]&&a[0]>1;a[0]--);???
}???
?????
mul(bignum_t b,monospace!important; min-height:auto!important; background:none!important">d)???
{???
i ;???
*)b,monospace!important; min-height:auto!important; background:none!important">(bignum_t));???
(b[0]=a[0]+d,i=d+1;i<=b[0];i++)???
((b[i]+=a[i-d]*c)>=DEPTH)???
b[i+1]+=b[i]/DEPTH,b[i]%=DEPTH ;???
(;b[b[0]+1];b[0]++,b[b[0]+1]=b[b[0]]/DEPTH,b[b[0]]%=DEPTH);???
(;!b[b[0]]&&b[0]>1;b[0]--);???
}???
/**************************************************************************/???
/* 大数相除,读入被除数a，除数b，结果保存在c[]数组???????????????????????? */???
/* 需要comp()函数???????????????????????????????????????????????????????? */???
/**************************************************************************/???
void?
div
(bignum_t c,bignum_t a,monospace!important; min-height:auto!important; background:none!important">bignum_t b)???
{???
h,l,m,i ;???
(bignum_t));???
c[0]=(b[0]<a[0]+1)?(a[0]-b[0]+2):1 ;???
(i=c[0];i;sub(a,b,c[i]=m,i-1),i--)???
(h=DEPTH-1,l=0,m=(h+l+1)>>1;h>l;m=(h+l+1)>>1)???
(comp(b,i-1,a))h=m-1 ;???
else?
l=m ;???
(;!c[c[0]]&&c[0]>1;c[0]--);???
c[0]=c[0]>1?c[0]:1 ;???
}???
?????
(bignum_t a,monospace!important; min-height:auto!important; background:none!important">b,
int
&c)???
{???
i ;???
(c=0,i=a[0];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);???
(;!a[a[0]]&&a[0]>1;a[0]--);???
}???
/************************************************************************/???
/* 大数平方根，读入大数a，结果保存在b[]数组里?????????????????????????? */???
/* 需要comp()函数?????????????????????????????????????????????????????? */???
/************************************************************************/???
sqrt
(bignum_t b,bignum_t a)???
{???
(bignum_t));???
(i=b[0]=(a[0]+1)>>1;i;sub(a,b[i]+=m,i--)???
l=m ;???
(;!b[b[0]]&&b[0]>1;b[0]--);???
(i=1;i<=b[0];b[i++]>>=1);???
}???
/************************************************************************/???
/* 返回大数的长度?????????????????????????????????????????????????????? */???
/************************************************************************/???
length(
bignum_t a)???
{???
t,ret ;???
(ret=(a[0]-1)*DIGIT,t=a[a[0]];t;t/=10,ret++);???
ret>0?ret:1 ;???
}???
/************************************************************************/???
/* 返回指定位置的数字，从低位开始数到第b位，返回b位上的数?????????????? */???
/************************************************************************/???
digit(
b)???
{???
(ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT;i;ret/=10,i--);???
ret%10 ;???
}???
/************************************************************************/???
/* 返回大数末尾0的个数????????????????????????????????????????????????? */???
/************************************************************************/???
zeronum(
bignum_t a)???
{???
ret,t ;???
(ret=0;!a[ret+1];ret++);???
(t=a[ret+1],ret*=DIGIT;!(t%10);t/=10,ret++);???
ret ;???
}???
?????
comp(
*a,monospace!important; min-height:auto!important; background:none!important">l,monospace!important; min-height:auto!important; background:none!important">d)???
{???
(i=l;i<=h;i++)???
(t=i,j=2;t>1;j++)???
while
(!(t%j))???
a[j]+=d,t/=j ;???
}???
?????
convert(
{???
(b,monospace!important; min-height:auto!important; background:none!important">(bignum_t));???
(b[0]=b[1]=1,i=2;i<=h;i++)???
(a[i])???
(j=a[i];j;t*=i,j--)???
(t*i>DEPTH)???
mul(b,t),t=1 ;???
}???
/************************************************************************/???
/* 组合数?????????????????????????????????????????????????????????????? */???
/************************************************************************/???
combination(bignum_t a,monospace!important; min-height:auto!important; background:none!important">m,monospace!important; min-height:auto!important; background:none!important">n)???
{???
*t=
new?
[m+1];???
*)t,monospace!important; min-height:auto!important; background:none!important">(
)*(m+1));???
comp(t,n+1,1);???
convert(t,a);???
delete
[]t ;???
}???
/************************************************************************/???
/* 排列数?????????????????????????????????????????????????????????????? */???
/************************************************************************/???
permutation(bignum_t a,monospace!important; min-height:auto!important; background:none!important">n)???
{???
(a,monospace!important; min-height:auto!important; background:none!important">(bignum_t));???
a[0]=a[1]=1 ;???
(i=m-n+1;i<=m;t*=i++)???
(t*i>DEPTH)???
mul(a,t=1 ;???
}???
????
#define SGN(x) ((x)>0?1:((x)<0?-1:0))???
#define ABS(x) ((x)>0?(x):-(x))???
?????
&sgn,istream&is=cin)???
{???
str[MAX*DIGIT+2],ch,*buf ;???
(bignum_t));???
(!(is>>str))
0 ;???
buf=str,sgn=1 ;???
(*buf==
'-'
)sgn=-1,buf++;???
);???
(i=1;i<=a[0];i++)???
;???
(;!a[a[0]]&&a[0]>1;a[0]--);???
(a[0]==1&&!a[1])sgn=0 ;???
1 ;???
}???
struct?
bignum????
{???
bignum_t num ;???
sgn ;???
public?
:???
inline?
bignum()???
{???
????????
(num,monospace!important; min-height:auto!important; background:none!important">(bignum_t));???
num[0]=1 ;???
sgn=0 ;???
}???
inline?
operator!()???
{???
num[0]==1&&!num[1];???
}???
bignum&operator=(
bignum&a)???
{???
memcpy
(bignum_t));???
sgn=a.sgn ;???
return
*
this?
;???
}???
a)???
{???
(bignum_t));???
num[0]=1 ;???
sgn=SGN (a);???
add(num,sgn*a);???
;???
}???
;???
bignum&operator+=(
bignum&a)???
{???
(sgn==a.sgn)add(num,a.num);???
else?
if????????????
(sgn&&a.sgn)???
{???
????????????
ret=comp(num,a.num);???
????????????
(ret>0)sub(num,a.num);???
(ret<0)???
????????????
{???
????????????????
bignum_t t ;???
????????????????
(t,num,monospace!important; min-height:auto!important; background:none!important">(bignum_t));???
(bignum_t));???
sub (num,t);???
sgn=a.sgn ;???
}???
else?
(bignum_t)),num[0]=1,sgn=0 ;???
}???
(!sgn)???
????????????
;???
}???
a)???
{???
(sgn*a>0)add(num,ABS(a));???
(sgn&&a)???
{???
int??
(ret<0)???
{???
bignum_t t ;???
(bignum_t));???
(bignum_t));???
num[0]=1 ;???
sgn=-sgn ;???
sub(num,t);???
}???
}???
if????
(!sgn)sgn=SGN(a),add(num,ABS(a));???
;???
}???
bignum operator+(
bignum&a)???
{???
bignum ret ;???
(ret.num,255)!important; background:none!important">sizeof?
(bignum_t));???
ret.sgn=sgn ;???
ret+=a ;???
ret ;???
}???
a)???
{???
bignum ret ;???
(bignum_t));???
ret.sgn=sgn ;???
ret+=a ;???
ret ;???
}???
bignum&operator-=(
bignum&a)???
{???
(sgn*a.sgn<0)add(num,a.num);???
if????????????
(sgn&&a.sgn)???
{???
(ret<0)???
{???
bignum_t t ;???
(bignum_t));???
(bignum_t));???
sgn=-sgn ;???
}???
}???
(!sgn)add (num,a.num),sgn=-a.sgn ;???
;???
}???
a)???
{???
(sgn*a<0)add(num,ABS(a));???
(sgn&&a)???
{???
(ret<0)???
{???
bignum_t t ;???
(bignum_t));???
(bignum_t));???
num[0]=1 ;???
sgn=-sgn ;???
}???
}???
if????
(!sgn)sgn=-SGN(a),ABS(a));???
;???
}???
bignum operator-(
bignum&a)???
{???
bignum ret ;???
(bignum_t));???
ret.sgn=sgn ;???
ret-=a ;???
ret ;???
}???
a)???
{???
bignum ret ;???
(bignum_t));???
ret.sgn=sgn ;???
ret-=a ;???
ret ;???
}???
bignum&operator*=(
bignum&a)???
{???
bignum_t t ;???
mul(t,a.num);???
(bignum_t));???
sgn*=a.sgn ;???
;???
}???
a)???
{???
mul(num,ABS(a));???
sgn*=SGN(a);???
;???
}???
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |