高精度模板

[2016-12-9]

重新写一下高精度模板(不要问我为什么)

自认为代码风格比较漂亮(雾

如果有更好的写法欢迎赐教 

---

封装结构体big

B是压位用的进制，W是每位长度

size表示长度，d[]就是保存的数字，倒着保存，从1开始

---

[2017-01-14]

update：修改一点bug，并且重载了运算符

[2017-02-16]

update：现在已经觉得这份代码没法看啦.........

[2017-03-25]

update：今天做一道题所以几乎重写了所有高精度...感觉不知道比以前高到哪里去了，以前的代码可能会有bug

这里放现在的代码：

struct Big{
    int a[120], n;
    int& operator [](int x) {return a[x];}
    Big():n(1) {memset(a, 0, sizeof(a));}
    void ini(int x) {a[1]=x; n=1;}
};

Big operator *(Big a, int b) {
    int g=0;
    for(int i=1; i<=a.n; i++) 
        g += a[i]*b, a[i] = g%B, g/=B;
    if(g) a[++a.n] = g;
    return a;
}

Big operator *(Big a, Big b) {
    Big c;
    for(int i=1; i<=a.n; i++) {
        int g=0;
        for(int j=1; j<=b.n; j++) 
            g += c[i+j-1]+a[i]*b[j], c[i+j-1] = g%B, g/=B;
        c[i+b.n] = g;
    }
    c.n = a.n + b.n;
    while(c.n>1 && c[c.n]==0) c.n--;
    return c;
}

Big operator +(Big a, Big b) {
    int g=0, n=max(a.n, b.n);
    for(int i=1; i<=n; i++) {
        g += i<=a.n ? a[i] : 0;
        g += i<=b.n ? b[i] : 0;
        a[i] = g%B, g/=B;
    }
    a.n = n;
    if(g) a[++a.n] = g;
    return a;
}

Big operator -(Big a, Big b) {
    for(int i=1; i<=b.n; i++) {
        if(a[i]<b[i]) a[i]+=B, a[i+1]--;
        a[i] -= b[i];
    }
    int p=b.n+1;
    while(a[p]<0) a[p]+=B, a[++p]--;
    while(a.n>1 && a[a.n]==0) a.n--;
    return a;
}

void Print(Big &a) {
    printf("%d", a[a.n]);
    for(int i=a.n-1; i>=1; i--) printf("%04d", a[i]);
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=2005,B=1e4,W=4,L=2005;

struct big{
    int size,d[L];
    big():size(0){memset(d,0,sizeof(d));}
};

//---------------------------------------------------
bool operator <(big &a,int b){//a<b
    if(a.size==1&&a.d[1]<b) return true;
    else return false;
}

big operator +(big a,int b){
    int t=a.d[1]+b,g=t/B;
    a.d[1]=t%B;
    for(int i=2;g;i++){//jin wei
        t=a.d[i]+g;
        a.d[i]=t%B;
        g=t/B;
        a.size=max(a.size,i);//update size
    }
    return a;
}
big operator -(big a,int b){
    if(a.d[1]<b){//jie wei
        a.d[1]+=B;
        int i;
        for(i=2;a.d[i]==0;i++) a.d[i]+=B-1;
        a.d[i]--;
        while(a.d[a.size]==0) a.size--;//update size
    }
    a.d[1]-=b;//last minus
    return a;
}
big operator *(big a,int b){
    int g=0;
    for(int i=1;i<=a.size;i++){//mul
        int t=a.d[i]*b+g;
        a.d[i]=t%B;
        g=t/B;
    }
    while(g){//jin wei
        a.d[++a.size]=g%B;//update size
        g/=B;
    }
    return a;
}
big operator /(big a,int b){
    int g=0;
    for(int i=a.size;i>=1;i--){//divide
        g=g*B+a.d[i];
        a.d[i]=g/b;
        g%=b;
    }
    while(a.d[a.size]==0) a.size--;//update size
    return a;
}

//---------------------------------------------------
bool operator <(big a,big b){//a<b
    if(a.size!=b.size) return a.size<b.size;
    for(int i=1;i<=a.size;i++)
        if(a.d[i]!=b.d[i]) return a.d[i]<b.d[i];
    return false;//a==b
}
big operator +(big a,big b){
    int g=0,i;
    for(i=1;;i++){
        if(g==0&&i>a.size&&i>b.size) break;
        int t=g;
        t+=i<=a.size?a.d[i]:0;
        t+=i<=b.size?b.d[i]:0;
        a.d[i]=t%B;
        g=t/B;
    }
    a.size=i-1;//update size
    return a;
}
big operator -(big a,big b){
    for(int i=1;i<=b.size;i++){
        if(a.d[i]<b.d[i]){//jie wei
            int p=i+1;
            while(a.d[p]==0) p++;
            a.d[p]--;p--;
            while(p!=i) a.d[p--]+=B-1;
            a.d[i]+=B;
        }
        a.d[i]-=b.d[i];
    }
    while(a.d[a.size]==0) a.size--;
    if(a.size<=0) a.size=1;
    return a;
}
big operator *(big a,big b){
    big c;
    for(int i=1;i<=a.size;i++){
        int g=0;
        for(int j=1;j<=b.size;j++){
            c.d[i+j-1]+=a.d[i]*b.d[j]+g;
            g=c.d[i+j-1]/B;
            c.d[i+j-1]%=B;
        }
        c.d[i+b.size]=g;
    }
    c.size=a.size+b.size;
    while(c.d[c.size]==0) c.size--;
    if(c.size<=0) c.size=1;
    return c;
}

//---------------------------------------------------
//压位 B=1e4 W=4 
void scan(big &a,char s[]){//annoy B ,if B==10 you can directly use the string
    int len=strlen(s+1);
    int p=a.size=len/W+(len%W!=0);
    for(int i=1;i<=p;i++){
        int r=len-(i-1)*W,l=max(len-i*W+1,1);
        for(int j=l;j<=r;j++) a.d[i]=a.d[i]*10+s[j]-'0';
    }
}
void print(big &a){//When B==1e4;If B==10 just print
    printf("%d",a.d[a.size]);
    for(int i=a.size-1;i>=1;i--){
        if(a.d[i]<10) printf("000");
        else if(a.d[i]<100) printf("00");
        else if(a.d[i]<1000) printf("0");
        printf("%d",a.d[i]);
    }
    putchar('
');
}
//不压位 B=10 W=1
//void scan(big &a,char s[]){
//    int len=strlen(s+1);
//    a.size=len; 
//    for(int i=1;i<=len;i++) a.d[len-i+1]=s[i]-'0';
//}
//void print(big &a){
//    for(int i=a.size;i>=1;i--) printf("%d",a.d[i]);
//}

//---------------------------------------------------
char s[N];
big a,b;
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%s",s+1);scan(a,s);
    scanf("%s",s+1);scan(b,s);
    a=a*b;
    print(a);
}