高精度

高精度

对于大数，c++中没有可以有效存储的类型。python有自带高精。所以c++只能手写高精，处理大数四则运算问题。对于高精度，一般使用结构体，让代码更简洁。还要重载运算符，也是避免大量函数影响代码美观。

以下是模板，基本原理是列竖式的加减乘除

const int MAXL=2000;
struct Number{
    long long a[MAXL+10];
    Number(){memset(a,0,sizeof a);}
    Number(int x){
        for(int i=1;i<=MAXL;++i){
            a[i] = x%10;
            x /= 10;
        }
    }
    Number operator + (const Number B)const{
        Number C;
        for(int i=1;i<=MAXL;++i){
            C.a[i] += a[i]+B.a[i];
            if(C.a[i]>=10){
                C.a[i+1] += C.a[i]/10;
                C.a[i] %= 10;
            }
        }
        return C;
    }
    Number operator * (const long long x)const{
        Number C;
        for(int i=1;i<=MAXL;++i){
            C.a[i] += a[i]*x;
            if(C.a[i]>=10){
                C.a[i+1] += C.a[i]/10;
                C.a[i] %= 10;
            }
        }
        return C;
    }
    Number operator / (const long long x)const{
        Number C;
       	long long tmp=0;
        for(int i=MAXL;i>=0;--i){
            C.a[i] = (tmp*10+a[i])/x;
            tmp = (tmp*10+a[i])%x;
        }
        return C;
    }
    void print(){
        int i=MAXL;
        while(i>=1&&a[i]==0)--i;//要判边界
        if(i<1)putchar('0');
        for(;i>=1;--i){
			printf("%c",'0'+a[i]);
		}
        putchar('\n');
    }
};

应用，比如一些组合数学问题

Number C(int a,int b){
    Number res(1);
    for(int i=0;i<b;++i)
		res=res*(a-i);
    for(int i=1;i<=b;++i)
		res=res/i;
    return res;
}