高精度算法

只是发个板子。虽说似乎NOIp近几年一般都是取膜而不是高精了，但我还是担心会考，所以就复习了一下。

定义

用struct储存整个数和位数。整个数全部倒序方便计算。

struct bigint{
    int s[5005],len;
    bigint(){memset(s,0,sizeof(s));len=0;}
};

加法

inline bigint add(bigint x,bigint y)
{
    bigint z;
    int len=max(x.len,y.len),add=0;
    for (int i=1;i<=len;i++)
    {
        z.s[i]=x.s[i]+y.s[i]+add;
        add=z.s[i]/10;
        z.s[i]%=10;
    }
    if (add) z.s[++len]=add;
    z.len=len;
    return z;
}

减法

和加法原理相同，不过这里保证x>y。所以

inline bigint sub(bigint x,bigint y) //x>y
{
    bigint z;
    int add=0,len=x.len;
    for (int i=1;i<=len;i++)
    {
        z.s[i]=x.s[i]-y.s[i]-add;
        add=0;
        if (z.s[i]<0) add=1,z.s[i]+=10;
    } 
    z.len=len;
    return z;
}

乘法

高精乘低精

原理也差不多，只是注意最后要把进位全部加完。

inline bigint times(bigint x,int y)
{
    bigint z;
    int len=x.len,add=0;
    for (int i=1;i<=len;i++)
    {
        z.s[i]=x.s[i]*y+add;
        add=z.s[i]/10;
        z.s[i]%=10;
    }
    while (add) 
    {
        z.s[++len]=add%10;
        add/=10;
    }
    z.len=len;
    return z;
}

高精乘高精

写过了，但还没写成模板，暂时先咕咕咕了。

upd:2018.11.9 (NOIp前一天) 把这个flag拔了

bigint times(bigint x,bigint y)
{
    bigint z;
    int lx=x.len,ly=y.len;
    for (int i=1;i<=lx;i++)
    {
        int add=0;
        for (int j=1;j<=ly;j++)
        {
            int now=x.s[i]*y.s[j]+add;
            z.s[i+j-1]+=now%10;
            if (z.s[i+j-1]>=10) z.s[i+j-1]-=10,z.s[i+j]++;
            add=now/10;
        }
        if (add) z.s[i+ly]+=add;
    }
    z.len=lx+ly;
    while (!z.s[z.len]) z.len--;
    return z;
}

除法

高精除低精

跟竖式一样，需要正着从高位往低位除。最后注意下把前导0去掉。

inline bigint division(bigint x,int y)
{
    bigint z;
    int sum=0,len=x.len;
    for (int i=len;i;i--)
    {
        sum=sum*10+x.s[i];
        z.s[i]=sum/y;
        sum%=y;
    }
    while (!z.s[len]) len--;
    z.len=len;
    return z;
}

高精除高精

写不来，noip估计也不会考。我太菜了。

比较大小

返回1表示 $ x>y $ ,-1表示 $ x<y $ ,0表示 $ x=y $。按位比较即可。

inline int cmp(bigint x,bigint y)
{
    if (x.len>y.len) return 1;
    if (x.len<y.len) return -1;
    for (int i=x.len;i;i--)
    {
        if (x.s[i]<y.s[i]) return -1;
        if (x.s[i]>y.s[i]) return 1;
    }
    return 0;
}

输出

逆序输出即可。

inline void print(bigint x)
{
    for (int i=x.len;i;i--)
        printf("%d",x.s[i]);
}

清空

把数组和长度都赋为0。

inline void clear(bigint &x)
{
    for (int i=1;i<=x.len;i++)
        x.s[i]=0;
    x.len=0;
}