以前是想把自己的博客变成技术博客的，可是前两篇写了点自己的一些事情，这次要发点技术性的东西了，ACM竞赛方面的大数类
代码：
const int base=10000; //数组中每个单元的基
const int basewidth=4; //数组中每个单元存储数的长度
const int capacity=10; //数组的大小，可以根据题意随意改变,basewidth*capacity等于最大位数
struct bignum //大数结构体
{
int len;
int data[capacity];
bignum():len(0){};
bignum& operator = (bignum& v)
{
len=v.len;
memcpy(data,v.data,sizeof(data));
return *this;
}
bignum& operator = (int v)
{
len=0;
for(;v>0;v/=base)
data[len++]=v%base;
return *this;
}
bignum& operator = (char* s)
{
len=0;
int l=strlen(s),sum=0,k=0;
if(l==1&&s[0]=='0') return *this;
if(l%basewidth){
for(int j=0;j<l%basewidth;j++) sum=sum*10+s[j]-'0';
data[len++]=sum;
}
sum=0;
for(int i=l%basewidth;i<l;i++){
sum=sum*10+s[i]-'0';
k+=1;
if(k==basewidth){
data[len++]=sum;
sum=k=0;
}
}
for(i=0;i<len/2;i++){
int r=data[i];
data[i]=data[len-1-i];
data[len-1-i]=r;
}
return *this;
}
};
int compare(bignum& a,bignum& b) //比较 a>b：1，a＝b：0,a<b：-1
{
int i;
if(a.len!=b.len) return a.len>b.len ? 1:-1;
for(i=a.len-1;i>=0&&a.data[i]==b.data[i];i--);
if(i<0) return 0;
return a.data[i]>b.data[i] ? 1:-1;
}
void add(bignum& a,bignum& b,bignum& r) //加法，两个数加起来放到r中
{
int i,carry=0;
for(i=0;i<a.len||i<b.len||carry>0;i++)
{
if(i<a.len) carry+=a.data[i];
if(i<b.len) carry+=b.data[i];
r.data[i]=carry%base;
carry/=base;
}
r.len=i;
}
void addto(bignum& a,bignum& b) //加法，两个数相加，结构存入a中
{
int i,carry=0;
for(i=0;i<a.len||i<b.len||carry>0;i++){
if(i<a.len) carry+=a.data[i];
if(i<b.len) carry+=b.data[i];
a.data[i]=carry%base;
carry/=base;
}
a.len=i;
}
void sub(bignum& a,bignum& b,bignum& r) //两个数相减，结果存入r中，条件是a>=b
{
int i,carry=0;
r.len=a.len;
for(i=0;i<r.len;i++)
{
r.data[i]=a.data[i]-carry;
if(i<b.len) r.data[i]-=b.data[i];
if(r.data[i]<0) carry=1,r.data[i]+=base;
else carry=0;
}
while(r.len>0&&r.data[r.len-1]==0) r.len--;
}
void subto(bignum& a,bignum& b) //两个数相减，结果存入a中，条件是a>=b
{
int i,carry=0;
for(i=0;i<a.len;i++)
{
a.data[i]-=carry;
if(i<b.len) a.data[i]-=b.data[i];
if(a.data[i]<0) carry=1,a.data[i]+=base;
else carry=0;
}
while(a.len>0&&a.data[a.len-1]==0) a.len--;
}
void mult(bignum& a,bignum& b,bignum& r) //乘法,注意不要超过r中data的限制
{
int i,j;
r.len=0;
if(b.len==0){ r.data[0]=0;return;}
for(i=0;i<a.len;i++)
{
int carry=0;
for(j=0;j<b.len||carry>0;j++)
{
if(j<b.len) carry+=a.data[i]*b.data[j];
if(i+j<r.len) carry+=r.data[i+j];
if(i+j>=r.len) r.data[r.len++]=carry%base;
else r.data[i+j]=carry%base;
carry/=base;
}
}
}
void mult(bignum& a,int b,bignum& r) //乘数是整数的情况,b<=10000
{
int i,carry=0;
r.len=0;
if(b==0){ r.data[0]=r.len=0;return;}
for(i=0;i<a.len||carry>0;i++)
{
if(i<a.len) carry+=a.data[i]*b;
r.data[i]=carry%base;
carry/=base;
}
r.len=i;
}
void multto(bignum& a,bignum& b){ //乘法，将结果保存到a中
bignum r;
mult(a,b,r);
a=r;
}
void multto(bignum& a,int b) //乘数是整数的情况,b<=10000,结果保存到a中
{
int i,carry=0;
if(b==0){ a.data[0]=a.len=0;return;}
for(i=0;i<a.len||carry>0;i++)
{
if(i<a.len) carry+=a.data[i]*b;
a.data[i]=carry%base;
carry/=base;
}
a.len=i;
}
void div(bignum& a,bignum& b,bignum& r,bignum& carry){//b>0,r=a/b,carry=a%b;用到mult,addto,compare,subto
bignum temp;
carry.data[0]=0;
carry.len=1;
int i,left,right,mid;
for(i=a.len-1;i>=0;i--){
mult(carry,base,temp);
carry=temp;
temp=a.data[i];
addto(carry,temp);
left=0,right=base-1;
while(left<right){
mid=(left+right+1)/2;
mult(b,mid,temp);
if(compare(temp,carry)<=0) left=mid;
else right=mid-1;
}
r.data[i]=left;
mult(b,left,temp);
subto(carry,temp);
}
r.len=a.len;
while(r.len>0&&r.data[r.len-1]==0) r.len--;
}
void divto(bignum& a,bignum& b,bignum& carry){ //b>0,a/=b,carry=a%b;用到mult,addto,compare,subto
bignum temp;
carry.data[0]=0;
carry.len=1;
int i,left,right,mid;
for(i=a.len-1;i>=0;i--){
mult(carry,base,temp);
carry=temp;
temp=a.data[i];
addto(carry,temp);
left=0,right=base-1;
while(left<right){
mid=(left+right+1)/2;
mult(b,mid,temp);
if(compare(temp,carry)<=0) left=mid;
else right=mid-1;
}
a.data[i]=left;
mult(b,left,temp);
subto(carry,temp);
}
while(a.len>0&&a.data[a.len-1]==0) a.len--;
}
void div(bignum& a,int& b,bignum& r,int& carry){ //0<b<10000,r=a/b,carry=a%b
int i;
carry=0;
for(i=a.len-1;i>=0;i--){
carry=carry*base+a.data[i];
r.data[i]=carry/b;
carry%=b;
}
r.len=a.len;
while(r.len>0&&r.data[r.len-1]==0) r.len--;
}
void divto(bignum& a,int& b,int& carry){ //0<b<10000,a/=b,carry=a%b
int i;
carry=0;
for(i=a.len-1;i>=0;i--){
carry=carry*base+a.data[i];
a.data[i]=carry/b;
carry%=b;
}
while(a.len>0&&a.data[a.len-1]==0) a.len--;
}
void bignumtochar(bignum a,char* b){ //将整形数变成字符串
if(a.len==0){ b[0]='0';b[1]='{post.abstract}';return;}
int j=base/10,k=0;
for(;a.data[a.len-1]<j;j/=10);
while(j){
b[k++]=a.data[a.len-1]/j+'0';
a.data[a.len-1]%=j;
j/=10;
}
for(int i=a.len-2;i>=0;i--){
for(j=base/10;j>0;j/=10){
b[k++]=a.data[i]/j+'0';
a.data[i]%=j;
}
}
b[k++]='{post.abstract}';
}
void write(bignum& v){ //输出函数
int i;
printf("%d",v.len==0?0:v.data[v.len-1]);
for(i=v.len-2;i>=0;i--) printf("%04d",v.data[i]); //根据basewidth来修改"%04d"的值
printf("\n");
}
