高精度运算

大整数运算（1000位以内）：

数是反向存储的，如123456，则d[0]=6，d[1]=5；

 

结构体：

struct bign{
    int d[1000];
    int len;
    bign(){
        memset(d,0,sizeof(d));
        len=0;    
    }
};

　　

将整数转换为bign：

bign change(char str[]){
    bign a;
    a.len=strlen(str);
    for(int i=0;i<a.len;i++){
        a[i]=a[a.len-i-1]-'0';
    }
    return a;
}

　　

大整数比较：

int compare(bign a,bign b){
    if(a.len>b.len) return 1;
    else if(a.len<b.len) return -1;
    else{
        for(int i=a.len-1;i>=0;i--){
            if(a[i]>b[i]) return 1;
            else if(a[i]<b[i]) return -1;
        }
        return 0;
    }
}

四则运算：

struct bign{
    int d[1000];
    int len;
    bign(){
        memset(d,0,sizeof(d));
        len=0;
    }
};
bign add(bign a,bign b){
    bign c;
    int carry=0;
    for(int i=0;i<a.len||i<b.len;i++){//以长的为界
        int temp=a.d[i]+b.d[i]+carry;
        c.d[i]=temp%10;
        carry=temp/10;
    }
    if(carry!=0){
        c.d[c.len++]=carry;
    }
    return c;
}

bign sub(bign a,bign b){
    bign c;
    for(int i=0;i<a.len||i<b.len;i++){
        if(a.d[i]<b.d[i]){   //不够减
            a.d[i+1]--;  //向高位借位
            a.d[i]+=10;  //当前位加10
        }
        c.d[c.len++]=a.d[i]-b.d[i];
    }
    while(c.len>=2&&c.d[c.len-1]==0){
        c.len--;  //去除高位0
    }
    return c;
}

bign multi(bign a,int b){    //注意这里是int b，乘法与小学乘法不同，将b当做整体，用a的低位开始乘，如147*35，7*35,4*35，1*35
    bign c;
    int carry=0;
    for(int i=0;i<a.len;i++){
        int temp=a.d[i]*b+carry;
        c.d[c.len++]=temp%10;
        carry=temp/10;
    }
    while(carry!=0){
        c.d[c.len++]=carry%10;
        carry/=10;
    }
    return c;
}

bign divide(bign a,int b,int& r) { //r为余数
    bign c;
    c.len=a.len;
    for(int i=len-1;i>=0;i--){
        r=r*10+a.d[i];
        if(r<b) c.d[i]=0;//不够除，该位为0
        else{
            c.d[i]=r/b;
            r=r%b;
        }
    }
    while(c.len>=2&&c.d[c.len-1]==0){
        c.len--;
    }
    return c;
}