高精度整理

结构体介绍

struct node
{
    int a[10010]={0};

    int& operator [] (int x)
    {
        return a[x];
    }

    void print()
    {
        for(int i=a[0];i>0;i--) printf("%d",a[i]);
    }
};

高精度加法

node operator + (node a,node b)//高精度加法
{
    int t=0,j=0;
    node res;
    int len=max(a[0],b[0]);

    int i=0;
    while(t||j||i<=len)
    {
        res[0]=i++;
        t=a[i]+b[i]+j;
        j=t/10;
        res[i]=t%10;
    }
    return res;
}

高精度减法

node operator - (node a,node b)//高精度减法
{
    int len=a[0];
    node res;
    for(int i=1,t=0;i<=len+10;i++)
    {
        t=a[i]-t;
        t-=b[i];
        res[i]=(t+10)%10;
        if(t<0) t=1;
        else t=0;
    }
    res[0]=len+10;
    while(!res[res[0]]&&res[0]>1) res[0]--;
    return res;
}

高精度乘低精度

node operator * (node a,int b)//高精度乘低精度
{
    int t=0,j=0,len=a[0];
    node res;

    int i=0;
    while(t||j||i<=len)
    {
        res[0]=i++;
        t=a[i]*b+j;
        j=t/10;
        res[i]=t%10;
    }
    return res;
}

上面模板已经被卡掉了

原因是，对于超大数据而言，$res[i]=t\mod10$这一行出现问题。

新版更新如下：

node operator * (node a,int b)
{
    int t=0,len=a[0];
    node res;
    int i=0;
    while(t||i<=len)
    {
        res[0]=++i;
        if(i<=len) t+=a[i]*b;
        res[i]=t%10;
        t/=10;
    }
    return res;
}

另外一个更好用的版本：

node operator * (node a,ll b)
{
    node res;
    res[0]=a[0];
    ll t=0;
    for(int i=1;i<=a[0];i++)
    {
        t+=a[i]*b;
        res[i]=t%10;
        t/=10;
    }
    while(t) res[++res[0]]=t%10,t/=10;
    return res;
}

挖坑，有空写高精度乘高精度

高精度乘高精度

高精度除以低精度

node operator / (node a,int b)//高精度除以低精度
{
    int t=0;
    node res;
    res[0]=a[0];

    for(int i=a[0];i>0;i--)
    {
        t=t*10+a[i];
        res[i]=t/b;
        t%=b;
    }
    while(!res[res[0]]&&res[0]>1) res[0]--;
    return res;
}

高精度除以高精度

如果需要保留 $n$ 位小数，那么将除数乘 $10^{n+2}$ 或 $10^{n+3}$ 位即可达到目的，但是仍然存在精度问题。

node devide(node a,node b)//高精度除以高精度
{
    node t,res;
    res[0]=a[0];
    t[0]=1;

    for(int i=a[0];i>0;i--)
    {
        node num;
        num[0]=1,num[1]=a[i];
        t=t*10;
        t=t+num;
        int cnt=0;
        while(!(b>t))
        {
            t=t-b;
            cnt++;
        }
        res[i]=cnt;
    }
    while(!res[res[0]]&&res[0]>1) res[0]--;

    return res;
}