C++ 压位高精度

苏宇锋

（2022.11.15 更正了代码中的一些bug）
普通的高精度算法都是一位只存放一个数字，但是我们这样显然浪费了大量的空间，一个 int 可以存放超过 2\times10^9 大小的数，考虑利用 int 的多位有效数字，可以大大减少常数
由于有乘法操作，一般我们为了防止溢出，会只使用 int 的最低 4 位，但是也可以看情况使用 8 位，最后第 9 位留着防止加法溢出，乘法就可以使用 long long 在中途当作临时变量
当然直接使用 long long 压位也是可以的
正好以前没写过高精板子，现在练练手
基础属性

class __int256
{
private:
    const static int N=2333,base=1e8;//N为压位后最大位数，base为压多少位
    int a[N],len,neg;//a存放int，len存放压位后位数，neg表示是否为负数
}
初始化

和不压位高精度类似的，每次模 base 的余数放进数组，再把这个数不断除以 base
template<typename _Tp>__int256(_Tp x)
{
    len=0;neg=0;
    memset(a,0,sizeof(a));
    if(x<0)x=-x,neg=1;
    int tmp;
    while((tmp=x/base))
    {
        a[++len]=x%base;
        x=tmp;
    }
    a[++len]=x;
}
比较运算

bool operator==(const __int256& x)const
{
    if(len!=x.len||neg!=x.neg)return false;
    for(int i=1;i<=len;++i)if(a!=x.a)return false;
    return true;
}
bool operator!=(const __int256& x)const{return !(*this==x);}
bool operator>(const __int256& x)const
{
    if(neg!=x.neg)return x.neg;
    if(len!=x.len)return len>x.len;
    for(int i=len;i;--i)if(a!=x.a)return a>x.a;
    return false;
}
bool operator<(const __int256& x)const
{
    if(neg!=x.neg)return neg;
    if(len!=x.len)return len<x.len;
    for(int i=len;i;--i)if(a!=x.a)return a<x.a;
    return false;
}
bool operator>=(const __int256& x)const{return !(*this<x);}
bool operator<=(const __int256& x)const{return !(*this>x);}
高精加高精

与普通高精加法类似，直接逐位相加，如果有进位就减掉 base 并让下一位加 1 就好，注意最高位进位的处理
__int256 operator+(const __int256& x)const
{
    if((!neg)&&x.neg)return *this-(-x);
    if(neg&&(!x.neg))return x-(-*this);
    __int256 ans=__int256();
    ans.len=std::max(len,x.len);
    for(int i=1;i<=ans.len;++i)
    {
        ans.a+=a+x.a;
        if(ans.a>=base)ans.a-=base,++ans.a[i+1];
    }
    if(ans.a[ans.len+1])++ans.len;
    if(neg&&x.neg)ans.neg=1;
    return ans;
}
高精减高精

同样的，只是注意必须要用更大的数减去更小的数，不然借位很难处理，同时前导零也不要忘记去除
__int256 operator-(const __int256& x)const
{
    if((!neg)&&x.neg)return *this+(-x);
    if(neg&&x.neg)return (-x)-(-*this);
    if(neg&&(!x.neg))return -((-*this)+x);
    __int256 ans=__int256();
    if(*this==x)return ans;
    if(x>*this)
    {
        ans=(x-*this);
        ans.neg=1;
        return ans;
    }
    ans.len=std::max(len,x.len);
    for(int i=1;i<=ans.len;++i)
    {
        ans.a+=a-x.a;
        if(ans.a<0)ans.a+=base,--ans.a[i+1];
    }while(ans.len&&!ans.a[ans.len])
        --ans.len;
    return ans;
}
高精乘高精

模拟竖式乘法，乘法分配律逐个相乘相加，复杂度 \Theta(\text{len}^2)
写 FFT 也可以，会更快一点（\Theta(\text{len}\log\text{len})），但是我太懒了
__int256 operator*(const __int256& x)const
{

    __int256 ans=__int256();
    if(*this==ans||x==ans)return ans;
    if(neg!=x.neg)ans.neg=1;
    ans.len=len+x.len;
    ull tmp;
    for(int i=1;i<=len;++i)
        for(int j=1;j<=x.len;++j)
        {
            tmp=1ull*a*x.a[j]+ans.a[i+j-1];
            if(tmp>=base)
            {
                ans.a[i+j]+=tmp/base;
                ans.a[i+j-1]=tmp%base;
            }
            else ans.a[i+j-1]=tmp;
        }while(!ans.a[ans.len])
            --ans.len;
    return ans;
}
高精乘低精

由于压位问题，如果压位位数很少，乘上一个较大的低精度数就会出现奇怪错误，所以就先转换成高精度再乘就好
高精除低精

直接模拟竖式除法，很简单没什么好说的
template<typename _Tp>__int256 operator/(const _Tp& x)const
{
    if(x==0)std::cerr<<"Error:divide 0\n",exit(-1);
    __int256 ans=__int256();
    if(len==1&&x>a[1])return ans;
    ull res=0;ans.len=len;
    if(neg!=(x<0))ans.neg=1;
    for(int i=len;i;--i)
    {
        res=res*base+a;
        ans.a=res/x;
        res%=x;
    }
    while(ans.len>1&&!ans.a[ans.len])--ans.len;
    return ans;
}
高精除高精

这里利用倍增，把除数倍增然后不断往下减，减掉之后再除以 2 接着减就行，由于使用了高精乘以低精和高精除以除以低精，所以常数会非常大，但是算是比较方便的一种实现了
__int256 operator/(const __int256& X)const
{
    if(X==0)std::cerr<<"Error:divide 0\n",exit(-1);
    __int256 ans(*this),x(X),tmp(1),lt=__int256();
    if(neg!=x.neg)ans.neg=1;
    while(ans>=x) x*=2,tmp*=2;
    while(tmp.len>1||tmp.a[1])
    {
        if(ans>=x) ans-=x,lt+=tmp;
        x/=2,tmp/=2;
    }
    ans=lt;
    while(ans.len&&!ans.a[ans.len])--ans.len;
    if(!ans.len)return __int256();
    return ans;
}
高精模高精和高精模低精

在高精除低精的过程中由于是模拟的竖式计算，最后自然会得到余数
在高精除高精的过程中由于我们是一直减去除数的倍数，最后也会得到余数
直接返回就行
__int256 operator%(const __int256& X)const
{
    if(X==0)std::cerr<<"Error:mod 0\n",exit(-1);
    __int256 ans(*this),x(X),tmp(1),lt=__int256();
    if(neg!=x.neg)ans.neg=1;
    while(ans>=x) x*=2,tmp*=2;
    while(tmp.len>1||tmp.a[1])
    {
        if(ans>=x) ans-=x,lt+=tmp;
        x/=2,tmp/=2;
    }
    return ans;
}
template<typename _Tp>__int256 operator%(const _Tp& x)const
{
    if(x==0)std::cerr<<"Error:mod 0\n",exit(-1);
    if(len==1&&x>a[1])return *this;
    ull res=0;
    for(int i=len;i;--i)
    {
        res=res*base+a;
        res%=x;
    }
    return res;
}
最终封装版

最后简单用 class 封装了一下，利用了 template 以实现与其他类型的更高的兼容度
里面还内置一个输入输出函数，同时重载了输入输出流，非常方便
namespace BigInteger
{
    typedef long long ll;
    typedef unsigned long long ull;
    class __int256
    {
    private:
        const static int N=105,base=1e8;
        int a[N],len,neg;
        void write(int _a)const{if(_a>9)write(_a/10);putchar((_a%10)|48);}
        int getlen(int _a)const{int ans=0;while(_a)_a/=10,++ans;return ans;}
    public:
        __int256(){len=1,neg=0,memset(a,0,sizeof(a));}
        __int256(char *s)
        {
            memset(a,0,sizeof(a));
            if(s[0]=='-')
            {
                int slen=strlen(s)-1;
                len=1,neg=1;
                int k=1;
                for(int i=1;i<=slen;++i)
                {
                    if(k==base)++len,k=1;
                    a[len]+=k*(s[slen-i+1]^48);
                    k*=10;
                }
            }
            else
            {
                int slen=strlen(s);
                len=1,neg=0;
                int k=1;
                for(int i=1;i<=slen;++i)
                {
                    if(k==base)++len,k=1;
                    a[len]+=k*(s[slen-i]^48);
                    k*=10;
                }
            }
        }
        __int256(std::string s)
        {
            memset(a,0,sizeof(a));
            if(s[0]=='-')
            {
                int slen=s.size()-1;
                len=1,neg=1;
                int k=1;
                for(int i=1;i<=slen;++i)
                {
                    if(k==base)++len,k=1;
                    a[len]+=k*(s[slen-i+1]^48);
                    k*=10;
                }
            }
            else
            {
                int slen=s.size();
                len=1,neg=0;
                int k=1;
                for(int i=1;i<=slen;++i)
                {
                    if(k==base)++len,k=1;
                    a[len]+=k*(s[slen-i]^48);
                    k*=10;
                }
            }
        }
        __int256(const char *s)
        {
            memset(a,0,sizeof(a));
            if(s[0]=='-')
            {
                int slen=strlen(s)-1;
                len=1,neg=1;
                int k=1;
                for(int i=1;i<=slen;++i)
                {
                    if(k==base)++len,k=1;
                    a[len]+=k*(s[slen-i+1]^48);
                    k*=10;
                }
            }
            else
            {
                int slen=strlen(s);
                len=1,neg=0;
                int k=1;
                for(int i=1;i<=slen;++i)
                {
                    if(k==base)++len,k=1;
                    a[len]+=k*(s[slen-i]^48);
                    k*=10;
                }
            }
        }
        template<typename _Tp>__int256(_Tp x)
        {
            len=0;neg=0;
            memset(a,0,sizeof(a));
            if(x<0)x=-x,neg=1;
            int tmp;
            while((tmp=x/base))
            {
                a[++len]=x%base;
                x=tmp;
            }
            a[++len]=x;
        }
        void get()
        {
            std::string s=std::string();
            char ch=getchar();
            while(ch<'0'||ch>'9')
            {
                if(ch=='-'&&!s.size())s+='-';
                ch=getchar();
            }
            while(ch>='0'&&ch<='9')s+=ch,ch=getchar();
            *this=__int256(s);
        }
        void print()const
        {
            int baselen=getlen(base)-1;
            if(neg)putchar('-');
            write(a[len]);
            for(int i=len-1,tmp;i;--i)
            {
                tmp=baselen-getlen(a);
                while(tmp--)putchar('0');
                if(a)write(a);
            }
        }
        std::string to_string()
        {
            std::string res="";
            int baselen=getlen(base)-1;
            if(neg)res+="-";
            std::string tmp1="";int tmp2=a[len];
            if(!a[len])return "0";
            while(tmp2)tmp1+=tmp2%10+'0',tmp2/=10;
            reverse(tmp1.begin(),tmp1.end());res+=tmp1;
            for(int i=len-1,tmp;i;--i)
            {
                tmp=baselen-getlen(a);
                while(tmp--)res+="0";
                if(!a)continue;
                tmp1="";tmp2=a;
                while(tmp2)tmp1+=tmp2%10+'0',tmp2/=10;
                reverse(tmp1.begin(),tmp1.end());res+=tmp1;
            }
            return res;
        }
        friend std::istream& operator>>(std::istream& input,__int256& x)
        {
            x.get();
            return input;
        }
        friend std::ostream& operator<<(std::ostream& output,const __int256& x)
        {
            x.print();
            return output;
        }
        bool operator==(const __int256& x)const
        {
            if(len!=x.len||neg!=x.neg)return false;
            for(int i=1;i<=len;++i)if(a!=x.a)return false;
            return true;
        }
        bool operator!=(const __int256& x)const{return !(*this==x);}
        bool operator>(const __int256& x)const
        {
            if(neg!=x.neg)return x.neg;
            if(len!=x.len)return len>x.len;
            for(int i=len;i;--i)if(a!=x.a)return a>x.a;
            return false;
        }
        bool operator<(const __int256& x)const
        {
            if(neg!=x.neg)return neg;
            if(len!=x.len)return len<x.len;
            for(int i=len;i;--i)if(a!=x.a)return a<x.a;
            return false;
        }
        bool operator>=(const __int256& x)const{return !(*this<x);}
        bool operator<=(const __int256& x)const{return !(*this>x);}


        __int256 operator-()const{__int256 x(*this);x.neg^=1;return x;}
        __int256 operator+(const __int256& x)const
        {
            if((!neg)&&x.neg)return *this-(-x);
            if(neg&&(!x.neg))return x-(-*this);
            __int256 ans=__int256();
            ans.len=std::max(len,x.len);
            for(int i=1;i<=ans.len;++i)
            {
                ans.a+=a+x.a;
                if(ans.a>=base)ans.a-=base,++ans.a[i+1];
            }
            if(ans.a[ans.len+1])++ans.len;
            if(neg&&x.neg)ans.neg=1;
            return ans;
        }
        __int256 operator+=(const __int256& x){return *this=*this+x;}
        __int256 operator-(const __int256& x)const
        {
            if((!neg)&&x.neg)return *this+(-x);
            if(neg&&x.neg)return (-x)-(-*this);
            if(neg&&(!x.neg))return -((-*this)+x);
            __int256 ans=__int256();
            if(*this==x)return ans;
            if(x>*this)
            {
                ans=(x-*this);
                ans.neg=1;
                return ans;
            }
            ans.len=std::max(len,x.len);
            for(int i=1;i<=ans.len;++i)
            {
                ans.a+=a-x.a;
                if(ans.a<0)ans.a+=base,--ans.a[i+1];
            }while(ans.len&&!ans.a[ans.len])--ans.len;
            return ans;
        }
        __int256 operator-=(const __int256& x){return *this=*this-x;}
        __int256 operator*(const __int256& x)const
        {

            __int256 ans=__int256();
            if(*this==ans||x==ans)return ans;
            if(neg!=x.neg)ans.neg=1;
            ans.len=len+x.len;
            ull tmp;
            for(int i=1;i<=len;++i)
                for(int j=1;j<=x.len;++j)
            {
                tmp=1ull*a*x.a[j]+ans.a[i+j-1];
                if(tmp>=base)
                {
                    ans.a[i+j]+=tmp/base;
                    ans.a[i+j-1]=tmp%base;
                }
                else ans.a[i+j-1]=tmp;
            }while(!ans.a[ans.len])
                --ans.len;
            return ans;
        }
        __int256 operator*=(const __int256& x){return *this=*this*x;}
        __int256 operator/(const __int256& X)const
        {
            if(X==0)std::cerr<<"Error:divide 0\n",exit(-1);
            __int256 ans(*this),x(X),tmp(1),lt=__int256();
            if(neg!=x.neg)ans.neg=1;
            while(ans>=x) x*=2,tmp*=2;
            while(tmp.len>1||tmp.a[1])
            {
                if(ans>=x) ans-=x,lt+=tmp;
                x/=2,tmp/=2;
            }
            ans=lt;
            while(ans.len&&!ans.a[ans.len])--ans.len;
            if(!ans.len)return __int256();
            return ans;
        }
        __int256 operator/=(const __int256& X)
        {
            if(X==0)std::cerr<<"Error:divide 0\n",exit(-1);
            __int256 x(X),tmp(1),lt=__int256();
            if(neg!=x.neg)neg=1;
            else neg=0;
            while(*this>=x) x*=2,tmp*=2;
            while(tmp.len>1||tmp.a[1])
            {
                if(*this>=x) *this-=x,lt+=tmp;
                x/=2,tmp/=2;
            }
            *this=lt;
            while(len&&!a[len])--len;
            if(!len)return *this=__int256();
            return *this;
        }
        __int256 operator%(const __int256& X)const
        {
            if(X==0)std::cerr<<"Error:mod 0\n",exit(-1);
            __int256 ans(*this),x(X),tmp(1),lt=__int256();
            if(neg!=x.neg)ans.neg=1;
            while(ans>=x) x*=2,tmp*=2;
            while(tmp.len>1||tmp.a[1])
            {
                if(ans>=x) ans-=x,lt+=tmp;
                x/=2,tmp/=2;
            }
            return ans;
        }
        __int256 operator%=(const __int256& X)
        {
            if(X==0)std::cerr<<"Error:mod 0\n",exit(-1);
            __int256 x(X),tmp(1),lt=__int256();
            if(neg!=x.neg)neg=1;
            else neg=0;
            while(*this>=x) x*=2,tmp*=2;
            while(tmp.len>1||tmp.a[1])
            {
                if(*this>=x) *this-=x,lt+=tmp;
                x/=2,tmp/=2;
            }
            return *this;
        }

        template<typename _Tp>operator _Tp()const{return _Tp(a[1]);}
        template<typename _Tp>__int256 operator+(const _Tp& x)const{return *this+__int256(x);}
        template<typename _Tp>__int256 operator+=(const _Tp& x){return *this=*this+x;}
        template<typename _Tp>__int256 operator-(const _Tp& x)const{return *this-__int256(x);}
        template<typename _Tp>__int256 operator-=(const _Tp& x){return *this=*this-x;}
        template<typename _Tp>__int256 operator*(const _Tp& x)const{return *this*__int256(x);}
        template<typename _Tp>__int256 operator*=(const _Tp& x){return *this=*this*x;}
        template<typename _Tp>__int256 operator/(const _Tp& x)const
        {
            if(x==0)std::cerr<<"Error:divide 0\n",exit(-1);
            __int256 ans=__int256();
            if(len==1&&x>a[1])return ans;
            ull res=0;ans.len=len;
            if(neg!=(x<0))ans.neg=1;
            for(int i=len;i;--i)
            {
                res=res*base+a;
                ans.a=res/x;
                res%=x;
            }
            while(ans.len>1&&!ans.a[ans.len])--ans.len;
            return ans;
        }
        template<typename _Tp>__int256 operator/=(const _Tp& x){return *this=*this/x;}
        template<typename _Tp>__int256 operator%(const _Tp& x)const
        {
            if(x==0)std::cerr<<"Error:mod 0\n",exit(-1);
            if(len==1&&x>a[1])return *this;
            ull res=0;
            for(int i=len;i;--i)
            {
                res=res*base+a;
                res%=x;
            }
            return res;
        }
        template<typename _Tp>__int256 operator%=(const _Tp& x){return *this=*this%x;}
    };
    template<typename _Tp>const __int256 operator+(const _Tp& x,const __int256& y){return __int256(x)+y;}
    template<typename _Tp>const __int256 operator-(const _Tp& x,const __int256& y){return __int256(x)-y;}
    template<typename _Tp>const __int256 operator*(const _Tp& x,const __int256& y){return __int256(x)*y;}
    template<typename _Tp>const __int256 operator/(const _Tp& x,const __int256& y){return __int256(x)/y;}
    template<typename _Tp>const __int256 operator%(const _Tp& x,const __int256& y){return __int256(x)%y;}
};
如果发现有什么 bug 欢迎指正
<hr/>UPD：2022.10.10 更正了高精度模低精度代码中的一个错误以及重载的两个神秘的编译器未报错的语法错误
UPD：2022.11.15 更正了运算过程中位数错误，初始化时的符号错误，并添加了 to_string() 功能，感谢 @ctldragon 的贡献！
博客园传送门
知乎传送门

河南医疗

太好用了，已经过了1919810^{114514}道紫题啦[大笑]

苏剑斌

在传 int 类型初始化中没有初始化 neg，导致传入一个正数的话 neg 不是 0。

英雄草

似乎压位有点锅（当__int256(10000000)*10的时候进位是错的

樊斌

ok我试试改一下

倪小平

找到bug了，进位的时候只判了当前位是否为 0，可能当前位为 0 更高位有值，这样长度就错了[大哭]

天山红

两种乘法都错了，最后调整len的时候不能直接加，中间可能压位后还是0，len只能减

倪小平

云剪贴板 - 洛谷
帮你改了改，还有关于中间0的输出的小问题。

自由撰稿人丶牵手

[爱]，不过在压位很小的时候如果用高精度乘很大的低精度还是会出问题，+20的话太怪了，还是先转换成高精再算好了，非常感谢 CCCCCOrz