高精度大全

· · 个人记录

高精加法:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2000;
const int base=10000;
char a[maxn],b[maxn];
struct bigint
{
    int cnt;
    ll a[maxn];
    bigint(){cnt=0;memset(a,0,sizeof(a));}
    inline void clear(){while(!a[cnt]&&cnt>1)cnt--;}//清除前导0
    inline void print()//输出
    {
        printf("%lld",a[cnt]);
        for(int i=cnt-1;i;i--)printf("%04lld",a[i]);
        puts("");
    }
    inline void init2(ll x)//用long long赋值
    {
        cnt=0;memset(a,0,sizeof(a));
        while(x)a[++cnt]=x%base,x/=base;
    } 
    inline void init2(char* s)//用字符串赋值
    {
        cnt=1;memset(a,0,sizeof(a));
        int len=strlen(s+1);
        for(int i=len,j=1;i;i--)
        {
            if(j==base)j=1,cnt++;
            a[cnt]+=(s[i]-'0')*j;j*=10;
        }
    }
}A,B,C;
bigint operator +(bigint x,bigint y)//高精加
{   
    bigint res;res.cnt=max(x.cnt,y.cnt);
    ll k=0ll;
    for(int i=1;i<=res.cnt;i++)
    {
        res.a[i]=x.a[i]+y.a[i]+k;
        k=res.a[i]/base;
        res.a[i]%=base;
    }
    if(k)res.a[++res.cnt]=k;
    return res;
}
int main()
{
    scanf("%s%s",a+1,b+1);
    A.init2(a),B.init2(b);
    //A.print();B.print();
    C=A+B;
    C.print();
    return 0;
}

高精减法:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200000;
const int base=10000;
char a[maxn],b[maxn];
struct bigint
{
    int cnt;
    ll a[maxn];
    bigint(){cnt=0;memset(a,0,sizeof(a));}
    inline void clear(){while(!a[cnt]&&cnt>1)cnt--;}
    inline void print() 
    {
        printf("%lld",a[cnt]);
        for(int i=cnt-1;i;i--)printf("%04lld",a[i]);
        puts("");
    }
    inline void init2(ll x)
    {
        cnt=0;memset(a,0,sizeof(a));
        while(x)a[++cnt]=x%base,x/=base;
    } 
    inline void init2(char* s)
    {
        cnt=1;memset(a,0,sizeof(a));
        int len=strlen(s+1);
        for(int i=len,j=1;i;i--)
        {
            if(j==base)j=1,cnt++;
            a[cnt]+=(s[i]-'0')*j;j*=10;
        }
    }
    bool operator<(const bigint& x)const
    {
        if(cnt==x.cnt)
        {
            int i;
            for(i=cnt;a[i]==x.a[i]&&i>1;i--);
            if(i>=1)return a[i]<x.a[i];
            else return 0;
        }
        else return cnt<x.cnt;
    }
}A,B,C;
bigint operator-(bigint x,bigint y)
{
    if(x<y)putchar('-'),swap(x,y);
    bigint res=x;int len=x.cnt;
    for(int i=1;i<=len;i++)
    {
        res.a[i]-=y.a[i];
        if(res.a[i]<0)res.a[i+1]--,res.a[i]+=base;
    }
    res.clear();
    return res;
}
int main()
{
    scanf("%s%s",a+1,b+1);
    A.init2(a),B.init2(b);
    //A.print();B.print();
    C=A-B;
    C.print();
    return 0;
}

高精乘法:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200000;
const int base=10000;
char a[maxn],b[maxn];
struct bigint
{
    int cnt;
    ll a[maxn];
    bigint(){cnt=0;memset(a,0,sizeof(a));}
    inline void clear(){while(!a[cnt]&&cnt>1)cnt--;}
    inline void print() 
    {
        printf("%lld",a[cnt]);
        for(int i=cnt-1;i;i--)printf("%04lld",a[i]);
        puts("");
    }
    inline void init2(ll x)
    {
        cnt=0;memset(a,0,sizeof(a));
        while(x)a[++cnt]=x%base,x/=base;
    } 
    inline void init2(char* s)
    {
        cnt=1;memset(a,0,sizeof(a));
        int len=strlen(s+1);
        for(int i=len,j=1;i;i--)
        {
            if(j==base)j=1,cnt++;
            a[cnt]+=(s[i]-'0')*j;j*=10;
        }
    }
}A,B,C;
bigint operator*(bigint x,bigint y)
{
    bigint res;res.cnt=x.cnt+y.cnt;
    for(int i=1;i<=x.cnt;i++)
        for(int j=1;j<=y.cnt;j++)
        {
            res.a[i+j-1]+=x.a[i]*y.a[j];
            res.a[i+j]+=res.a[i+j-1]/base;
            res.a[i+j-1]%=base;
        }
    res.clear();
    return res;
}
int main()
{
    scanf("%s%s",a+1,b+1);
    A.init2(a),B.init2(b);
    //A.print();B.print();
    C=A*B;
    C.print();
    return 0;
}

高精除低精:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200000;
const int base=10000;
int k;
char s[maxn];
struct bigint
{
    int cnt;
    ll a[maxn];
    bigint(){cnt=0;memset(a,0,sizeof(a));}
    inline void clear(){while(!a[cnt]&&cnt>1)cnt--;}
    inline void print() 
    {
        printf("%lld",a[cnt]);
        for(int i=cnt-1;i;i--)printf("%04lld",a[i]);
        puts("");
    }
    inline void init2(ll x)
    {
        cnt=0;memset(a,0,sizeof(a));
        while(x)a[++cnt]=x%base,x/=base;
    } 
    inline void init2(char* s)
    {
        cnt=1;memset(a,0,sizeof(a));
        int len=strlen(s+1);
        for(int i=len,j=1;i;i--)
        {
            if(j==base)j=1,cnt++;
            a[cnt]+=(s[i]-'0')*j;j*=10;
        }
    }
}A,B,C;
bigint operator/(bigint x,int y)
{
    bigint res;res.cnt=x.cnt;
    ll k=0ll;
    for(int i=x.cnt;i;i--)
    {
        k=k*base+x.a[i];
        res.a[i]=k/y;
        k%=y;
    }
    res.clear();
    return res;
} 
int main()
{
    scanf("%s%d",s+1,&k);
    A.init2(s);
    C=A/k;
    C.print();
    return 0;
}

高精除高精:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=110;
const int base=10;
char a[maxn],b[maxn];
struct bigint
{
    ll cnt;
    ll a[maxn];
    bigint(){cnt=0;memset(a,0,sizeof(a));}
    inline void clear(){while(!a[cnt]&&cnt>1)cnt--;}
    inline void print() 
    {
        printf("%lld",a[cnt]);
        for(int i=cnt-1;i;i--)printf("%lld",a[i]);
        puts("");
    }
    inline void init1(ll x)
    {
        cnt=0;memset(a,0,sizeof(a));
        while(x)a[++cnt]=x%base,x/=base;
    } 
    inline void init2(char* s)
    {
        cnt=1;memset(a,0,sizeof(a));
        int len=strlen(s+1);
        for(int i=len,j=1;i;i--)
        {
            if(j==base)j=1,cnt++;
            a[cnt]+=(s[i]-'0')*j;j*=10;
        }
    }
    inline void add(ll k)
    {
        if(!k&&cnt==1&&!a[1])return;//!!
        for(int i=cnt;i;i--)a[i+1]=a[i];
        a[1]=k;cnt++;
    }
    bool operator<(const bigint& x)const
    {
        if(cnt==x.cnt)
        {
            int i;
            for(i=cnt;a[i]==x.a[i]&&i>1;i--);
            if(i>=1)return a[i]<x.a[i];
            else return 0;
        }
        else return cnt<x.cnt;
    }
}A,B,C;
bigint operator-(bigint x,bigint y)
{
    bigint res=x;
    for(int i=1;i<=x.cnt;i++)
    {
        res.a[i]-=y.a[i];
        if(res.a[i]<0)res.a[i+1]--,res.a[i]+=base;
    }
    res.clear();
    return res;
}
bigint operator/(bigint x,bigint y)
{
    bigint res,k;res.cnt=x.cnt;
    for(int i=x.cnt;i;i--)
    {
        k.add(x.a[i]);
        while(!(k<y))k=k-y,res.a[i]++;
    }
    res.clear();
    return res;
}
int main()
{
    scanf("%s%s",a+1,b+1);
    A.init2(a),B.init2(b);
    C=A/B;
    C.print();
    return 0;
}