# 高精度模板

# 一、高精度简介

什么时候用高精度呢，很简单，当你的答案大到练$long long$ 都存不下去的时候，高精度就派上用场了。一般的高精度时间复杂度为$O(n^2)$ 的，优化过后的算法可以降低到$O(n^{1.57})$，但一般的题目中用最朴素的高精度就可以解决大多数问题，因此只上了一般的高精度代码

# 二、例题和代码

例题：A+B Problem plus

例题：A*B Problem plus

例题：A/B Problem plus

Code:

struct biglong
{
    int d[N],fh;

    void print()
    {
        d[1]*=fh;
        for(int i=1;i<=d[0];i++)
            printf("%d",d[i]);
        printf("\n");
    }

    bool operator < (const biglong & ot) const
    {
        if(d[0]==ot.d[0])
        {
            for(int i=1;i<=d[0];i++)
            {
                if(d[i]==ot.d[i])
                    continue;
                return d[i]<ot.d[i];
            }
        }
        return d[0]<ot.d[0];
    }

    biglong operator + (biglong & ot)
    {
        biglong t;
        memset(t.d,0,sizeof(t.d));
        for(int a=1,b=d[0];a<b;a++,b--)
            swap(d[a],d[b]);
        for(int a=1,b=ot.d[0];a<b;a++,b--)
            swap(ot.d[a],ot.d[b]);
        int borrow=0;
        t.d[0]=max(d[0],ot.d[0]);
        for(int i=1;i<=t.d[0];i++)
        {
            t.d[i]=borrow+d[i]+ot.d[i];
            if(t.d[i]>=10)
                borrow=t.d[i]/10,t.d[i]%=10;
            else
                borrow=0;
        }
        if(borrow>0)
            t.d[0]++,t.d[t.d[0]]=borrow;
        for(int a=1,b=d[0];a<b;a++,b--)
            swap(d[a],d[b]);
        for(int a=1,b=ot.d[0];a<b;a++,b--)
            swap(ot.d[a],ot.d[b]);
        for(int a=1,b=t.d[0];a<b;a++,b--)
            swap(t.d[a],t.d[b]);
        return t;
    }

    biglong operator * (biglong & ot)
    {
        biglong t;
        memset(t.d,0,sizeof(t.d));
        for(int a=1,b=d[0];a<b;a++,b--)
            swap(d[a],d[b]);
        for(int a=1,b=ot.d[0];a<b;a++,b--)
            swap(ot.d[a],ot.d[b]);
        for(int i=1;i<=d[0];i++)
        {
           for(int j=1;j<=ot.d[0];j++)
           {
                t.d[i+j-1]+=d[i]*ot.d[j];
                t.d[i+j]+=t.d[i+j-1]/10;
                t.d[i+j-1]%=10;
           }
        }
        t.d[0]=d[0]+ot.d[0];
        while(t.d[t.d[0]]==0)
            t.d[0]--;
        for(int a=1,b=t.d[0];a<b;a++,b--)
            swap(t.d[a],t.d[b]);
        for(int a=1,b=d[0];a<b;a++,b--)
            swap(d[a],d[b]);
        for(int a=1,b=ot.d[0];a<b;a++,b--)
            swap(ot.d[a],ot.d[b]);
        return t;
    }
};

biglong zero;

biglong cut(biglong x,biglong y)
{
    biglong t;
    memset(t.d,0,sizeof(t.d));
    if(x<y)
    {
        biglong temp=zero;
        temp=x,x=y,y=temp;
        t.fh=-1;
    }
    else
        t.fh=1;
    for(int a=1,b=x.d[0];a<b;a++,b--)
        swap(x.d[a],x.d[b]);
    for(int a=1,b=y.d[0];a<b;a++,b--)
        swap(y.d[a],y.d[b]);
    int maxn=max(x.d[0],y.d[0]);
    for(int i=1;i<=maxn;i++)
    {
        if(x.d[i]<y.d[i])
        {
            x.d[i+1]--;
            x.d[i]+=10;
        }
        t.d[i]=x.d[i]-y.d[i];
    }
    while(t.d[maxn]==0)
        maxn--;
    t.d[0]=maxn;
    if(maxn<0)
        memset(t.d,0,sizeof(t.d)),t.d[0]=1;
    for(int a=1,b=t.d[0];a<b;a++,b--)
        swap(t.d[a],t.d[b]);
    return t;
}

biglong mul(biglong x,int v)
{
    biglong ans=zero;
    for(int a=1,b=x.d[0];a<b;a++,b--)
        swap(x.d[a],x.d[b]);
    int borrow=0;
    for(int t=1;t<=x.d[0] || borrow;t++)
    {
        ans.d[t]=x.d[t]*v+borrow;
        borrow=ans.d[t]/10;
        ans.d[t]%=10;
        ans.d[0]++;
    }
    for(int a=1,b=x.d[0];a<b;a++,b--)
        swap(x.d[a],x.d[b]);
    for(int a=1,b=ans.d[0];a<b;a++,b--)
        swap(ans.d[a],ans.d[b]);
    return ans;
}

biglong divison(biglong x,int cut)
{
    biglong ans1=zero,ans2=zero;
    int borrow=0;
    for(int i=1;i<=x.d[0];i++)
    {
        ans1.d[i]=(borrow*10+x.d[i])/cut;
        borrow=(borrow*10+x.d[i])%cut;
    }
    int len=1;
    while(ans1.d[len]==0 && len<x.d[0])
        len++;
    for(int i=1;i<=x.d[0]-len+1;i++)
        ans2.d[i]=ans1.d[i+len-1];
    ans2.d[0]=x.d[0]-len+1;
    return ans2;
}