压八位高精度高精操作大全-白红宇

压八位高精度高精操作大全

阅读量：4326 次

发布时间：2019-06-06

本文共 7454 字，大约阅读时间需要 24 分钟。

1.高精简单操作

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct bigint{    static const int base=1e+8;    static const int width=8;    int s[10001],tot;    bigint(long long num=0){*this=num;}    void lenth(){while(tot>0&&!s[tot-1]) --tot;}    bigint operator = (long long num){//        tot=0;        while(num){            s[tot++]=num%base;            num/=base;        }        this->lenth();        return *this;    }    bigint operator = (char* buf){//        tot=0;        int len=strlen(buf),x=0;        for(register int i=len-1;i>=0;i-=width){            x=0;            for(register int j=max(i-width+1,0);j<=i;++j) x=x*10+buf[j]-'0';            s[tot++]=x;        }        this->lenth();        return *this;    }    int& operator [] (int x){//        return s[x];    }    void print(){//        lenth();        if(!tot){            putchar('0');            return;        }        int p=tot-1;        printf("%d",s[p]);        for(p=tot-2;p>=0;--p) printf("%08d",s[p]);    }    bigint operator + (bigint b){//        bigint c=0;        int x=0;        for(register int i=0;i
         
          
           =0;--i){ if(a[i]!=b[i]) return a[i]
           
            =0;--i){ c[i]=(x*base+s[i])>>1; x=(s[i]&1); } c.lenth();/ return c; } bigint multi(){// long long x=0; bigint c=0; for(register int i=0;i

高精，GCD，stein.

即

gcd(a,b)=2*gcd(a/2,b/2);

gcd(a,b)=gcd(a/2,b);

gcd(a,b)=gcd(a,b/2);

再用辗转相减套个高精就好

2.高精除int

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int num[10001],l1=0;int res[10001],len=0;struct bigint{    static const int base=10;    static const int width=1;    int tot;    int s[10001];    bigint(long long num=0){(*this)=num;}    void lenth(){while(tot>0&&!s[tot-1]) --tot;}    int& operator [] (int n){        return s[n];    }    bigint operator = (long long num){        tot=0;        while(num){            s[tot++]=num%base;            num/=base;        }        this->lenth();        return *this;    }    bigint operator = (char* buf){        tot=0;        int len=strlen(buf);        for(register int i=len-1;i>=0;--i){            s[tot++]=buf[i]-'0';        }        this->lenth();        return *this;    }    bigint mul(int n){        long long x=0;        bigint c=0;        for(register int i=0;i
         
          =0;--p) printf("%d",s[p]);        return;    }    bigint div(int n){        if(n==1) return *this;        bigint c;        long long x=0;        /*for(register int i=tot-1;i>=0;--i){            if((s[i]+(x<<1)+(x<<3))>=n){                x=(x<<1)+(x<<3)+s[i];                c[i]=x/n;                c.tot++;                x%=n;            }            else{                x=(x<<1)+(x<<3)+s[i];            }        }*/        for(register int i=tot-1;i>=0;--i){            x=(x<<1)+(x<<3)+s[i];            c[i]=x/n;            x%=n;        }        c.tot=tot;        c.lenth();        return c;    }};bigint katalan(int n){    bigint c=1;    int N=(n<<1);    for(register int i=n+2;i<=N;++i)        c=c.mul(i);    for(register int i=1;i<=n;++i)        c=(c.div(i));    return c;}int main(){    int n;    bigint a;    scanf("%d",&n);    a=katalan(n);    a.print();    return 0;}

高精，katalan，组合数学.

即

暴力打表观察分析一下，易得答案为katalan数

递推显然是要T的，化简一波就好了

再套个高精，支持除非高精就行

3.高精乘高精

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct bigint{    static const int base=10;    static const int width=1;    int tot,s[10005];    bigint(long long num=0){*this=num;memset(s,0,sizeof(s));tot=0;}/memset?????     void lenth(){while(tot>0&&!s[tot-1])--tot;}    bigint operator = (long long num){        tot=0;        while(num){            s[tot++]=num%base;            num/=base;        }        this->lenth();        return *this;    }    /*bigint operator = (char* buf){        tot=0;        int len=strlen(buf),x=0;        for(register int i=len-1;i>=0;i-=width){            x=0;            for(register int j=max(i-width+1,0);j<=i;++j) x=(x<<1)+(x<<3)+(buf[j]^48);            s[tot++]=x;        }        this->lenth();        return *this;    } */    bigint operator = (string buf){        tot=0;        int len=buf.length(),x=0;        for(register int i=len-1;i>=0;i--){            x=0;            for(register int j=max(i-width+1,0);j<=i;++j) x=(x<<1)+(x<<3)+(buf[j]^48);            s[tot++]=x;        }        this->lenth();        return *this;    }     int& operator [] (int x){        return s[x];    }    friend bool operator < (bigint a,bigint b){        if(a.tot!=b.tot) return a.tot
         
          =0;--i){            if(a[i]!=b[i]) return a[i]
          
           =0;--p) printf("%d",s[p]); return; } void carry_up(){ int rep=tot-1; for(register int i=0;i
           
            =base){ s[i+1]+=s[i]/base; s[i]%=base; } } int estbit=tot-1,res=s[tot-1]/base; while(res){ ++estbit; res/=base; } //printf("the highest bit of the array is %d\n",estbit);//DEBUG for(register int i=tot-1;i<=estbit;++i){ if(s[i]>=base){ s[i+1]=s[i]/base; s[i]%=base; } } tot+=estbit+1; this->lenth(); return; } bigint multiply(bigint b){ bigint c=0; c.tot=0; if(tot>b.tot){ //printf("a.tot>b.tot\n"); // DEBUG for(register int i=0;i

高精，DP.

DP不难，高精乘高精倒是DEBUG了一晚上...

4.高精大全

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct bigint{    static const int base=1e+8;    static const int width=8;    int tot;    long long s[10005];    bigint(long long num=0){*this=num;memset(s,0,10005);tot=0;}    void lenth(){while(tot>0&&!s[tot-1]) --tot;}    bigint operator = (long long num){        tot=0;        while(num){            s[tot++]=num%base;            num/=base;        }        this->lenth();        return *this;    }    bigint operator = (char* buf){        tot=0;        int len=strlen(buf),x=0;        for(int i=len-1;i>=0;i-=width){            x=0;            for(int j=max(i-width+1,0);j<=i;++j)                x=x*10+buf[j]-48;            s[tot++]=x;        }        this->lenth();        return *this;    }    long long int& operator [](int x){        return s[x];    }    void print(){        lenth();        if(!tot){            putchar('0');            return;        }        int p=tot-1;        printf("%lld",s[p]);        for(p=tot-2;p>=0;p--)            printf("%08lld",s[p]);        return;    }    friend bool operator < (bigint a,bigint b){        if(a.tot!=b.tot) return a.tot
         
          =0;--i)            if(a[i]!=b[i]) return a[i]
          
           =base)?(s[i+1]+=s[i]/base,s[i]%=base):1; } int estbit=rep,res=s[rep]/base; while(res){ ++estbit; res/=base; } for(int i=tot-1;i<=estbit;i++){ (s[i]>=base)?(s[i+1]+=s[i]/base,s[i]%=base):1; } tot+=estbit+1; this->lenth(); return; } bigint multiply(bigint b){ bigint c=0; c.tot=0; if(tot>b.tot){ for(int i=0;i
           
            =0;--i){ c[i]=(x*base+s[i])>>1; x=(s[i]&1); } c.lenth();/ return c; } bigint multi2(){// long long x=0; bigint c=0; for(register int i=0;i
            
             >=1; a=a.multiply(a); } return ans;}int m;char a[10005];int main(){// freopen("GG.out","r",stdin);// freopen("GGout.out","w",stdout); scanf("%d",&m); scanf("%s",a); bigint GG,r,l,mid,one,ans; one=1; GG=a; r=2; l=1; if(m==1){ GG.print(); return 0; } if(GG