Aoki_Umi

高精度算法——重载运算符

~~因为在一次模拟赛中因为高精吃了很大的亏，所以决定学习重载运算符后的高精度算法~~

~~所以打了一天~~

- 什么是重载运算符？

可以看这个博客

解释很详细，总之就是自定义运算
相当于把运算符重新自己定义
百科：运算符重载，就是对已有的运算符重新进行定义，赋予其另一种功能，以适应不同的数据类型。
大概就是这样，具体请参考我推荐的博客

- 如何实现

主要是通过结构体实现，在结构体中重新定义新的变量来进行定义新的运算符，具体看代码

- 如何运用到高精度计算

1. 初始化

struct BIGNUM
{
    int s[LEN<<1];//存储每一位数字
    bool flag;//判断负号
    BIGNUM()//初始化
    {
        memset(s,0,sizeof(s));
        flag=s[0]=1;
    }
    void init()
    {
        memset(s,0,sizeof(s));
        s[0]=1;
    }
}

2. 关系运算符重载

这个一定要先写因为在高精算法中会用到很多判定必须要先写这个，其实本质是字符串比大小

bool operator == (const BIGNUM &a)
    {
        int len=max(s[0],a.s[0]);
        for(int i=len;i>=1;i--)
            if(s[i]!=a.s[i])return false ;
        return true;
    }
    bool operator < (const BIGNUM &a)
    {
        if(s[0]==a.s[0])
        {
            for(int i=s[0];i>=1;i--)
            {
                if(s[i]<a.s[i])return true;
                if(s[i]>a.s[i])return false;
            }
            return false;
        }
        return s[0]<a.s[0];
    }
    bool operator > (const BIGNUM &a)
    {
        if(s[0] != a.s[0]) return s[0] > a.s[0];
        int up = max(s[0], a.s[0]);
        for(int i = 0; i < up; i++)
            if(s[up - i] != a.s[up - i]) return s[up - i] > a.s[up - i];
        return false;
    }
    bool operator >= (const BIGNUM &a)
    {
        if(*this > a||*this == a)return true;
        return false;
    }
    bool operator <= (const BIGNUM &a)
    {
        if(*this <a||*this == a)return true;
        return false;
    }

3.高精度加法

其实就是普通高精加法，只是用BIGNUM写的
重载了运算符

BIGNUM operator + (const BIGNUM &a)//大整数相加
    {
        BIGNUM c;
        int x=0;
        c.s[0]=max(a.s[0],s[0])+1;
        for(int i=1;i<=c.s[0];i++)
        {
            c.s[i]=a.s[i]+x+s[i];
            x=c.s[i]/10;
            c.s[i]%=10;

        }
        while(c.s[c.s[0]]==0&&c.s[0]>1)c.s[0]--;
        return c;
    }
BIGNUM operator += (const BIGNUM &a)
    {
        *this= *this + a;
        return *this;
    }

4. 高精度减法

普通字符串处理

BIGNUM operator - (const BIGNUM &a)//大整数相减
    {
        BIGNUM c;
        c.s[0]=max(s[0],a.s[0])+1;
        if(*this < a)c.flag =false;
        for(int i=1;i<=c.s[0];i++)
        {
            if(c.flag)c.s[i]+=s[i]-a.s[i];
            else c.s[i]+=a.s[i]-s[i];
            if(c.s[i]<0)
            {
                c.s[i]+=10;
                c.s[i+1]--;
            }
        }
        while(c.s[c.s[0]]==0&&c.s[0]>1)c.s[0]--;
        return c;
    }
BIGNUM operator -= (const BIGNUM &a)
    {
        *this =*this - a;
        return *this;
    }

5. 高精度乘法

不解释

BIGNUM operator * (const BIGNUM &a)//大整数乘法
    {
        BIGNUM c;
        c.s[0]=s[0]+a.s[0];
        for(int i=1;i<=s[0];i++)
        {
            int x=0;
            for(int j=1;j<=a.s[0];j++)
            {
                c.s[i+j-1]+=s[i]*a.s[j]+x;
                x=c.s[i+j-1]/10;
                c.s[i+j-1]%=10;

            }
            c.s[i+a.s[0]]=x;
        }
        while(c.s[c.s[0]]>0)c.s[0]++;
        while(c.s[c.s[0]]==0&&c.s[0]>1)c.s[0]--;
        return c;
    }
BIGNUM operator *= (const BIGNUM &a)
    {
        *this =*this * a;
        return *this;
    }

6. 高精度除法

BIGNUM operator / (const BIGNUM &a)//大整数除法
   {
        BIGNUM c, tmp;
        c.s[0] = s[0] - a.s[0] + 1;
        for(int i = c.s[0]; i >= 1; i--)
        {
            tmp.init();
            for(int j = 1; j <= a.s[0]; j++) 
               tmp.s[i + j - 1] = a.s[j];
            tmp.s[0] = a.s[0] + i - 1;
            while(*this >= tmp)
            {
                *this = *this - tmp;
                c.s[i]++;
            }
        }
        while(c.s[c.s[0]] == 0 && c.s[0] > 1) 
            c.s[0]--;
        if(c.s[0] < 1) c.s[c.s[0] = 1] = 0;
        return c;
    }
BIGNUM operator /= (const BIGNUM &a)
    {
        *this =*this /a;
        return *this;
    }

7. 高精度求余

BIGNUM operator % (const BIGNUM &a)//求余
    {
        BIGNUM d =*this,c= *this / a;
        c *= a;
        return d - c;
    }
    BIGNUM operator %= (const BIGNUM &a)
    {
        *this= *this % a;
        return *this;
    }

9. 输入输出大整数时修改的符号

ostream& operator << (ostream &out,const BIGNUM &a)
{
    if(!a.flag)putchar('-');
    for(int i=a.s[0];i>=1;i--)
    cout <<a.s[i];
    return out;
}
istream& operator >>(istream &in,BIGNUM &a)
{
    char str[LEN];
    in>> str;
    a=str;
    return in;
}

10. 赋值运算符重载

    BIGNUM (int num){ *this=num;}//将int型转化为BIGNUM
    BIGNUM (const char *num){*this=num;}//将char型转化为BIGNUM
    BIGNUM operator = (const char *num)//当=后面是char型，将char赋给BIGNUM
    {
        s[0]=strlen(num);
        for(int i=0;i<s[0];i++)s[i+1]=num[s[0]-1-i]-'0';
        return *this;
    }
    BIGNUM operator = (const int num)//当=后面int型，将int赋给BIGNUM
    {
        char a[LEN];
        sprintf(a,"%d",num);
        *this = a;
        return *this;
    }
    BIGNUM operator = (const BIGNUM &num)//当=后面是BIGNUM型，将BIGNUM赋给BIGNUM
    {
        int l=max(s[0],num.s[0]);
        for(int i=0;i<=l;i++)s[i]=num.s[i];

    }

- 总代码终极模板

#include<iostream>
#include<cstdio>
#include<cstring>
//注意千万不能偷懒写bits否则在除法时会出现奇怪的错误，就是那个program received signal sigsegv，后果非常惨重完全调不出来不要问我怎么知道的
using namespace std;

const int LEN = 10000 + 1;
//重载运算符的高精度(较完整版本)
//支持 高精度+ - * / %
//支持 += -= *= /= %=
//支持 < > >= <= 
struct BIGNUM
{
    int s[LEN<<1];//存储每一位数字
    bool flag;//判断负号
    BIGNUM()//初始化
    {
        memset(s,0,sizeof(s));
        flag=s[0]=1;
    }
    void init()
    {
        memset(s,0,sizeof(s));
        s[0]=1;
    }
    //-----------赋值运算符重载------------------------------------------------------------------------
    BIGNUM (int num){ *this=num;}//将int型转化为BIGNUM
    BIGNUM (const char *num){*this=num;}//将char型转化为BIGNUM
    BIGNUM operator = (const char *num)//当=后面是char型，将char赋给BIGNUM
    {
        s[0]=strlen(num);
        for(int i=0;i<s[0];i++)s[i+1]=num[s[0]-1-i]-'0';
        return *this;
    }
    BIGNUM operator = (const int num)//当=后面int型，将int赋给BIGNUM
    {
        char a[LEN];
        sprintf(a,"%d",num);
        *this = a;
        return *this;
    }
    BIGNUM operator = (const BIGNUM &num)//当=后面是BIGNUM型，将BIGNUM赋给BIGNUM
    {
        int l=max(s[0],num.s[0]);
        for(int i=0;i<=l;i++)s[i]=num.s[i];

    }
    //-------------关系运算符重载------------------------------------------------------------
    bool operator == (const BIGNUM &a)
    {
        int len=max(s[0],a.s[0]);
        for(int i=len;i>=1;i--)
            if(s[i]!=a.s[i])return false ;
        return true;
    }
    bool operator < (const BIGNUM &a)
    {
        if(s[0]==a.s[0])
        {
            for(int i=s[0];i>=1;i--)
            {
                if(s[i]<a.s[i])return true;
                if(s[i]>a.s[i])return false;
            }
            return false;
        }
        return s[0]<a.s[0];
    }
    bool operator > (const BIGNUM &a)
    {
        if(s[0] != a.s[0]) return s[0] > a.s[0];
        int up = max(s[0], a.s[0]);
        for(int i = 0; i < up; i++)
            if(s[up - i] != a.s[up - i]) return s[up - i] > a.s[up - i];
        return false;
    }
    bool operator >= (const BIGNUM &a)
    {
        if(*this > a||*this == a)return true;
        return false;
    }
    bool operator <= (const BIGNUM &a)
    {
        if(*this <a||*this == a)return true;
        return false;
    }
    //------------算数运算符重载------------------------------------------=---------------------
    BIGNUM operator + (const BIGNUM &a)//大整数相加
    {
        BIGNUM c;
        int x=0;
        c.s[0]=max(a.s[0],s[0])+1;
        for(int i=1;i<=c.s[0];i++)
        {
            c.s[i]=a.s[i]+x+s[i];
            x=c.s[i]/10;
            c.s[i]%=10;

        }
        while(c.s[c.s[0]]==0&&c.s[0]>1)c.s[0]--;
        return c;
    }
    BIGNUM operator += (const BIGNUM &a)
    {
        *this= *this + a;
        return *this;
    }
    BIGNUM operator - (const BIGNUM &a)//大整数相减
    {
        BIGNUM c;
        c.s[0]=max(s[0],a.s[0])+1;
        if(*this < a)c.flag =false;
        for(int i=1;i<=c.s[0];i++)
        {
            if(c.flag)c.s[i]+=s[i]-a.s[i];
            else c.s[i]+=a.s[i]-s[i];
            if(c.s[i]<0)
            {
                c.s[i]+=10;
                c.s[i+1]--;
            }
        }
        while(c.s[c.s[0]]==0&&c.s[0]>1)c.s[0]--;
        return c;
    }
    BIGNUM operator -= (const BIGNUM &a)
    {
        *this =*this - a;
        return *this;
    }
    BIGNUM operator * (const BIGNUM &a)//大整数乘法
    {
        BIGNUM c;
        c.s[0]=s[0]+a.s[0];
        for(int i=1;i<=s[0];i++)
        {
            int x=0;
            for(int j=1;j<=a.s[0];j++)
            {
                c.s[i+j-1]+=s[i]*a.s[j]+x;
                x=c.s[i+j-1]/10;
                c.s[i+j-1]%=10;

            }
            c.s[i+a.s[0]]=x;
        }
        while(c.s[c.s[0]]>0)c.s[0]++;
        while(c.s[c.s[0]]==0&&c.s[0]>1)c.s[0]--;
        return c;
    }
    BIGNUM operator *= (const BIGNUM &a)
    {
        *this =*this * a;
        return *this;
    }
   BIGNUM operator / (const BIGNUM &a)//大整数除法
   {
        BIGNUM c, tmp;
        c.s[0] = s[0] - a.s[0] + 1;
        for(int i = c.s[0]; i >= 1; i--)
        {
            tmp.init();
            for(int j = 1; j <= a.s[0]; j++) tmp.s[i + j - 1] = a.s[j];
            tmp.s[0] = a.s[0] + i - 1;
            while(*this >= tmp)
            {
                *this = *this - tmp;
                c.s[i]++;
            }
        }
        while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--;
        if(c.s[0] < 1) c.s[c.s[0] = 1] = 0;
        return c;
    }

    BIGNUM operator /= (const BIGNUM &a)
    {
        *this =*this /a;
        return *this;
    }

    BIGNUM operator % (const BIGNUM &a)//求余
    {
        BIGNUM d =*this,c= *this / a;
        c *= a;
        return d - c;
    }
    BIGNUM operator %= (const BIGNUM &a)
    {
        *this= *this % a;
        return *this;
    }

};
//--------------系统运算符-----------------------------------------------------------------------
ostream& operator << (ostream &out,const BIGNUM &a)
{
    if(!a.flag)putchar('-');
    for(int i=a.s[0];i>=1;i--)
    cout <<a.s[i];
    return out;
}
istream& operator >>(istream &in,const BIGNUM &a)
{
    char str[LEN];
    in>> str;
    a=str;
    return in;
}

BIGNUM a,b;
int main()
{
    cin>> a >> b ;
    cout<<a+b<<endl;
    cout<<a-b<<endl;
    cout<<a*b<<endl;
    cout<<a/b<<endl;
    cout<<a%b<<endl;
    return 0;
}