【SinGuLaRiTy-1042】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.

结构体封装

//高精度运算 注意%I64d与%lld#define LL long long intstruct bignum{    LL num[MAXN] ;    void init()    {        memset(num,0,sizeof num);    }        bool operator < (const bignum &a)const    {        if(num[0]!=a.num[0])return num[0]
     
      0;--i)            if(num[i]!=a.num[i])                return num[i]
      
       0)++num[0];    }        bignum operator + (const LL a)const    {        bignum temp=*this;        temp+=a;        return temp ;    }        void operator += (const bignum &a)    {        num[0]=max(num[0],a.num[0]);        for(int i=1;i<=num[0];++i)        {            num[i]+=a.num[i];            num[i+1]+=num[i]/mod;            num[i]%=mod;        }        while(num[num[0]+1]>0)++num[0];    }        bignum operator + (const bignum &a)const    {        bignum temp=*this;        temp+=a;        return temp;    }        void operator -= (const LL &a)    {        num[1]-=a;        for(int i=1;num[i]<0&&i<=num[0];++i)            while(num[i]<0)            {                num[i]+=mod;                --num[i+1];            }        while(num[num[0]]<=0&&num[0]>0)--num[0];    }        bignum operator - (const LL &a)const    {        bignum temp=*this;        temp-=a;        return temp ;    }        void operator -= (const bignum &a)    {        for(int i=1;i<=num[0];++i)        {            num[i]-=a.num[i];            while(num[i]<0)            {                num[i]+=mod ;                --num[i+1];            }        }        while(num[num[0]]<=0&&num[0]>0)--num[0];    }        bignum operator - (const bignum &a)const    {        bignum temp=*this;        temp-=a;        return temp;    }        void operator *= (const LL &a)    {        for(int i=1;i<=num[0];++i)            num[i]*=a;        for(int i=1;i<=num[0];++i)        {            num[i+1]+=num[i]/mod;            num[i]%=mod;        }    }        bignum operator * (const LL &a)const    {        bignum temp=*this;        temp*=a;        return temp;    }        bignum operator * (const bignum &a)const    {        bignum c;        c.init();        c.num[0]=num[0]+a.num[0]-1;        for(int i=1;i<=num[0];++i)            for(int j=1;j<=a.num[0];++j)                c.num[i+j-1]+=num[i]*a.num[j];        for(int i=1;i<=c.num[0];++i)        {            c.num[i+1]+=c.num[i]/mod;            c.num[i]%=mod;        }        while(c.num[c.num[0]+1]>0)        {            ++c.num[0];            c.num[c.num[0]+1]+=c.num[c.num[0]]/mod;            c.num[c.num[0]]%=mod;        }        return c;    }        void operator *= (const bignum &a)    {        bignum c=*this;        c=c*a;        *this=c;    }        void operator /= (const LL &a)    {        for(int i=num[0];i>1;--i)        {            num[i-1]+=(num[i]%a*mod);            num[i]/=a;        }        num[1]/=a;        while(num[0]>0&&num[num[0]]<=0)--num[0];    }        bignum operator / (const LL &a)const    {        bignum temp=*this ;        temp/=a;        return temp;    }        void operator %= (const LL &a)    {        bignum temp=*this;        temp=temp-temp/a*a;        *this=temp;    }        bignum operator % (const LL &a)const    {        bignum temp=*this;        temp%=a;        return temp;    }        void operator /=(const bignum &a){        bignum l ,m ,r =*this;        l.init();        l.num[0]=1 ;        while(l
       
        0;--i)            printf("%08I64d",num[i]);        puts("");    }}
       
      
     

Main函数单独封装

加法

#include
     
      #include
      
       char a[1000],b[1000];char c[1000];int i;void swap(char a[]){    char tmp;    for(int i=0;i
       
        =10)            {                c[i]=c[i]-10;                c[i+1]=1;            }    }    if(strlen(a)==strlen(b))        if(c[i]==1)            c[i]='1';    if(strlen(a)>strlen(b))    {        if(c[i]==1)        {            for(;i
        
         =10)                {                    c[i]=c[i]-10;                    c[i+1]=1;                }            }            if(c[i-1]=='0')                c[i]='1';        }        else            for(;i
         
          strlen(a))    {        if(c[i]==1)        {            for(;i
          
           =10) { c[i]=c[i]-10; c[i+1]=1; } } if(c[i]==1) c[i]='1'; } else for(;i
          
         
        
       
      
     

减法

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;char a[1001],b[1001];int a1[1001],b1[1001];int c[1001];int i,j,al,bl,l;int main(){ scanf("%s",a); scanf("%s",b); al=strlen(a); bl=strlen(b); l=al>bl?al:bl; for(i=0;i
           
            =0;i--) { if(al>bl || a1[i]>b1[i]) { for(j=0;j
            
             =0;j--) printf("%c",c[j]); break; } if(al
             
              
               =0;j--) printf("%c",c[j]); break; } } return 0;}
              
             
            
           
          
         
        
       
      
     

乘法

#include
     
      #include
      
       #include
       
        using namespace std;int jw,sum,ac,bc,k;int a,b,ans[10000];string A;string B;int main(){    cin>>A>>B;    ac=A.size()-1;    bc=B.size()-1;    for(int i=0;i<=ac;i++)    {        a=A[ac-i]-'0';        for(int j=0;j<=bc;j++)        {            k=i+j;            b=B[bc-j]-'0';            ans[k]+=a*b;            if(ans[k]>=10)            {                ans[k+1]+=ans[k]/10;                ans[k]%=10;            }        }    }    if(ans[k+1]>0)        k++;    for(int i=k;i>=0;i--)        cout<
       
      
     

开方

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           int l;int work(int o,char *O,int I){ char c,*D=O ; if(o>0) { for(l=0;D[l];D[l++]-=10) { D[l++]-=120; D[l]-=110; while(!work(0,O,l)) D[l]+=20; putchar((D[l]+1032)/20); } putchar(10); } else { c=o+(D[I]+82)%10-(I>l/2)*(D[I-l+I]+72)/10-9; D[I]+=I<0 ? 0 : !(o=work(c/10,O,I-1))*((c+999)%10-(D[I]+92)%10); } return o;}int main(){ char s[1200]; s[0]='0'; scanf("%s",s+1); if(strlen(s)%2==1) work(2,s+1,0); else work(2,s,0); return 0;}
          
         
        
       
      
     

整数除法

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;char s1[600],s2[600];int a1[600],a2[600],a3[600],a4[600],len1,len2,len3,i,j;int bi(int a3[],int a4[]){ if(a3[0]
           
            a4[0]) return 1; for(int i=a3[0];i>0;i--) { if(a3[i]
            
             a4[i]) return 1; } return 1;}int jian(int a3[],int a4[]){ for(int i=1;i<=a3[0];i++) { if(a3[i]
             
              1;a3[0]--);}int main(){ scanf("%s",s1); scanf("%s",s2); len1=strlen(s1); len2=strlen(s2); for(i=0;i
              
               0;i--) { memset(a3,0,sizeof(a3)); for(j=1;j<=a2[0];j++) a3[j+i-1]=a2[j]; a3[0]=a2[0]+i-1; for(;bi(a1,a3);) { a4[i]++; jian(a1,a3); } } for(;a4[a4[0]]==0&&a4[0]>1;a4[0]--); for(i=a4[0];i>0;i--) printf("%d",a4[i]); return 0;}
              
             
            
           
          
         
        
       
      
     

高精度非整除求余数除法

#include
     
      #include
      
       using namespace std;int a[101],b[101],c[101];int d,i;void init(int a[]){    string s;    cin>>s;    a[0]=s.length();    for(i=1;i<=a[0];i++)    {        a[i]=s[a[0]-i]-'0';    }}void print(int a[]){    int i;    if(a[0]==0)    {        cout<<0<
       
        0;i--)    {        cout<
        
         b[0])        return 1;    if(a[0]
         
          0;i--)    {        if(a[i]>b[i])            return 1;        if(a[i]
          
           0&&a[a[0]]==0) a[0]--; return; }}void numcpy(int p[],int q[],int det){ for(int i=1;i<=p[0];i++) { q[i+det-1]=p[i]; } q[0]=p[0]+det-1;}void Division(int a[],int b[],int c[]){ int i,tmp[101]; c[0]=a[0]-b[0]+1; for(i=c[0];i>0;i--) { memset(tmp,0,sizeof(tmp)); numcpy(b,tmp,i); while(compare(a,tmp)>=0) { c[i]++; subtraction(a,tmp); } } while(c[0]>0&&c[c[0]]==0) c[0]--; return;}int main(){ memset(a,0,sizeof(a)); memset(b,0,sizeof(a)); memset(c,0,sizeof(a)); init(a); init(b); Division(a,b,c); print(c); print(a); return 0;}
          
         
        
       
      
     

*四则高精度混合运算

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define MAXN 1000struct hp{    int a[MAXN+10];    hp(){        memset(a,0,sizeof a);        a[0]=1;    }    hp(int n){        memset(a,0,sizeof a);        a[0]=0;        while(n){            a[++a[0]]=n%10;            n/=10;        }        if(!a[0])            a[0]=1;    }    hp(char *s){        memset(a,0,sizeof a);        int len=strlen(s);        for(int i=1;i<=len;i++)            a[i]=s[len-i]-'0';        a[0]=len;    }    hp operator*(const hp &b)const{        hp c;        int i,j,len=a[0]+b.a[0];        for(i=1;i<=a[0];i++)            for(j=1;j<=b.a[0];j++)                c.a[i+j-1]+=a[i]*b.a[j];        for(i=1;i
         
          1&&!c.a[len])            len--;        c.a[0]=len;        return c;    }    hp operator/(int b)const{        hp c;        int d=0,i,len=a[0];        for(i=a[0];i;i--){            d=d*10+a[i];            c.a[i]=d/b;            d%=b;        }        while(len>1&&!c.a[len])            len--;        c.a[0]=len;        return c;    }    hp operator+(const hp &b)const{        hp c;        int len=max(a[0],b.a[0]),i;        for(i=1;i<=len;i++){            c.a[i]+=a[i]+b.a[i];            c.a[i+1]=c.a[i]/10;            c.a[i]%=10;        }        len++;        while(len>1&&!c.a[len])            len--;        c.a[0]=len;        return c;    }    hp operator-(const hp &b)const{        hp c;        int i,len=a[0];        for(i=1;i<=len;i++){            c.a[i]+=a[i]-b.a[i];            if(c.a[i]<0)                c.a[i]+=10,c.a[i+1]--;        }        while(len>1&&!c.a[len])            len--;        c.a[0]=len;        return c;    }    void operator*=(const hp &x){        *this=*this*x;    }    void operator/=(const int &x){        *this=*this/x;    }    void operator+=(const hp &x){        *this=*this+x;    }    void operator-=(const hp &x){        *this=*this-x;    }    void print(){        for(int i=a[0];i;i--)            printf("%d",a[i]);    }    bool operator>(const hp&b)const{        if(a[0]>b.a[0])            return 1;        if(a[0]
          
           b.a[i]) return 1; else if(a[i]
           
            b.a[0]) return 0; for(int i=a[0];i;i--) if(a[i]
            
             b.a[i]) return 0; return 0; } bool operator<=(const hp&b)const{ return !(*this>b); } hp operator/(const hp&b)const{ hp l(0),r(*this),mid; while(l
            
           
          
         
        
       
      
     

 

Time: 2017-10-16