高精度缺省源

Prean · 2021-07-02 08:30:00 · 个人记录

RT，因为最近教练讲的题多半都需要高精度，就写了这么一个东西。。。

欢迎同学们来贺我写的板子（

#include<cstdio>
const int M=1e5+5,mod=1e8;
const int p10[8]={1,10,100,1000,10000,100000,1000000,10000000};
inline int max(const int&a,const int&b){
    return a>b?a:b;
}
inline int Add(const int&a,const int&b){
    return a+b>=mod?a+b-mod:a+b;
}
struct Int{
    int len,a[M];
    Int():len(0){}
    Int(const int&x){
        a[len=1]=x;
    }
    inline int&operator[](const int&id){
        return a[id];
    }
    inline void input(){
        static char s[M];
        scanf("%s",s+1);len=1;
        while(s[len])++len;--len;
        for(register int i=1;i<=len;++i)a[(i-1>>3)+1]+=(s[len-i+1]^48)*p10[i-1&7],s[len-i+1]=0;
        len=(len-1>>3)+1;
    }
    inline void output(){
        printf("%d",a[len]);
        for(register int i=len-1;i>=1;--i)printf("%08d",a[i]);
    }
    inline Int operator+(Int b)const{
        Int c;c.len=max(len,b.len);
        for(register int i=1;i<=c.len;++i)c[i]=a[i]+b[i];
        for(register int i=1;i<=c.len;++i){
            if(c[i]>=mod)++c[i+1],c[i]-=mod;
        }
        if(c[c.len+1])++c.len;
        return c;
    }
    inline Int operator-(Int b)const{
        Int c;c.len=max(len,b.len);
        for(register int i=1;i<=c.len;++i)c[i]=a[i]-b[i];
        for(register int i=c.len;i>=1;--i){
            if(c[i]<0)--c[i+1],c[i]+=mod;
        }
        while(!c[c.len])--c.len;
        return c;
    }
    inline Int operator*(Int b)const{
        static long long tmp[M];Int c;c.len=len+b.len-1;
        for(register int i=1;i<=len;++i){
            for(register int j=1;j<=b.len;++j){
                tmp[i+j-1]+=1ll*a[i]*b[j];
            }
        }
        for(register int i=1;i<=c.len;++i){
            if(tmp[i]>=mod)c[i]=Add(c[i],tmp[i]%mod),c[i+1]=tmp[i]/mod;
            else c[i]=Add(c[i],tmp[i]);tmp[i]=0;
        }
        if(c[c.len+1]){
            if(c[++c.len]>=mod)c[c.len+1]=c[c.len]/mod,c[c.len]%=mod;
        }
        return c;
    }
    inline Int&operator+=(const Int&b){
        return *this=*this+b;
    }
    inline Int&operator-=(const Int&b){
        return *this=*this-b;
    }
    inline Int&operator*=(const Int&b){
        return *this=*this*b;
    }
};