/*用于大数的处理的类,目前仅支持"+","-","*"运算.
作者:Killer懒猫
开发时间:2005-05-30
版本 1.0
希望大家指点帮助，并完善它。

类有关说明:
所有运算元素为字符数组,大小为longs,默认为1000位
运算结果需要使用char类数组保存.
加法函数add,前两数加,结果保存在第三个数组中
减法函数sub,前两数减,结果保存在第三个数组中
乘法函数mult,前两数乘,结果保存在第三个数组中
初始化函数tozero把运算元素初始化为0
设置函数setlong设置运算元素大小(非结果大小)
*/
#include<string.h>
class bignum{
public:
    void add(char *,char *,char *);
    void sub(char *,char *,char *);
    void mult(char *,char *,char *);
    void tozero(char *a){a[0]='0';a[1]='\0';}
    bignum(int a=1000){longs=a;}
    void setlong(int a){longs=a;}
private:
    int max(int a,int b){return a>b?a:b;}
    int numlong(char *);
    void reverse(char *);
    void addzero(char *,char *);
    void subzero(char *);
    int longs;
};
int bignum::numlong(char *a)
{
    int i=0;
    while(a[i++]);
    return i-1;
}
void bignum::reverse(char *a)
{
    int i;
    char c;
    int longc=numlong(a);
    for(i=0;i<longc/2;i++){
        c=a[i];
        a[i]=a[longc-1-i];
        a[longc-1-i]=c;
    }
}
void bignum::addzero(char *numa,char *numb)
{
    int longa=numlong(numa);
    int longb=numlong(numb);
    int maxlong=max(longa,longb)+1;
    int tlonga=longa;
    int tlongb=longb;
    int i;
    for(i=0;i<(maxlong-tlonga);i++)
        numa[longa++]='0';
    numa[longa]='\0';
    for(i=0;i<(maxlong-tlongb);i++)
        numb[longb++]='0';
    numb[longb]='\0';
}
void bignum::subzero(char *a)
{
    int i=0;
    while(a[i++]);
    i=i-2;
    while(a[i]=='0'){
        a[i]='\0';
        i--;
        if(i==0&&a[i]=='0')
            return;
    }
}
void bignum::add(char *numa,char *numb,char *a)
{
    char *tnuma,*tnumb;
    int longa,longb;
    int maxab,i,temp=0;
    tnuma=new char[longs];tnumb=new char[longs];
    strcpy(tnuma,numa);strcpy(tnumb,numb);
    reverse(tnuma);reverse(tnumb);
    addzero(tnuma,tnumb);
    longb=numlong(tnumb);
    longa=numlong(tnuma);
    maxab=max(longa,longb);
    for(i=0;i<maxab;i++){
        if(tnuma[i]+tnumb[i]-2*'0'+temp<10){
            a[i]=tnuma[i]+tnumb[i]-'0'+temp;
            temp=0;
        }
        else{
            a[i]=(tnuma[i]+tnumb[i]-2*'0'+temp)%10+'0';
            temp=1;
        }
    }
    a[i]='\0';
    subzero(a);
    reverse(a);
    delete[] tnuma;delete[] tnumb;
}
void bignum::sub(char *numa,char *numb,char *a)
{
    int longab,i=0,temp=0;
    char *temps,c='\0';
    char *tnuma,*tnumb;
    tnuma=new char[longs];tnumb=new char[longs];temps=new char[longs];
    strcpy(tnuma,numa);strcpy(tnumb,numb);    
    reverse(tnuma);reverse(tnumb);
    addzero(tnuma,tnumb);
    longab=numlong(tnuma);
    i=longab-2;
    if(tnuma[i]-tnumb[i]<0){
        c='-';
        strcpy(temps,tnuma);
        strcpy(tnuma,tnumb);
        strcpy(tnumb,temps);
    }
    for(i=0;i<longab;i++){
        if(tnuma[i]-tnumb[i]-temp>=0){
            a[i]=tnuma[i]-tnumb[i]-temp+'0';
            temp=0;}
        else{
            a[i]=tnuma[i]-tnumb[i]-temp+10+'0';
            temp=1;}
    }
    a[i]='\0';
    subzero(a);
    if(c=='-')
        a[numlong(a)]=c;
    reverse(a);
    delete[] tnuma;delete[] tnumb;delete[] temps;
}
void bignum::mult(char *numa,char *numb,char *a)
{
    int tblong=numlong(numb)-1;
    char *tnuma;
    int i,j,pp,tempj=tblong;
    tnuma=new char[longs];
    strcpy(tnuma,numa);
    tozero(a);
    for(j=tblong;j>=0;j--){
        for(i=(numb[j]-'0');i>0;i--){
            while(tempj!=j){
                pp=numlong(tnuma);
                tnuma[pp]='0';
                tnuma[pp+1]='\0';
                tempj--;
            }
            add(a,tnuma,a);
        }
    }
    delete[] tnuma;
}