首页 > 其他分享 >压位高精度封装

压位高精度封装

时间：2022-10-07 17:13:09浏览次数：85  
标签：__ 封装 高精度 压位 return int256 len ans const

C++ 压位高精度封装模板

普通的高精度算法都是一位只存放一个数字，但是我们这样显然浪费了大量的空间，一个 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)
{
    memset(a,0,sizeof(a));
    if(x<0)x=-x,neg=1;
    len=0;
    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[i]!=x.a[i])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[i]!=x.a[i])return a[i]>x.a[i];
    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[i]!=x.a[i])return a[i]<x.a[i];
    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[i]+=a[i]+x.a[i];
        if(ans.a[i]>=base)ans.a[i]-=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[i]+=a[i]-x.a[i];
        if(ans.a[i]<0)ans.a[i]+=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=std::max(len,x.len);
    ull tmp;
    for(int i=1;i<=len;++i)
        for(int j=1;j<=x.len;++j)
        {
            tmp=1ull*a[i]*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]>0)++ans.len;
    --ans.len;
    return ans;
}

高精乘低精

和高精加法很像，每次临时放在 long long 或者 unsigned long long 暂时存一下就行了

template<typename _Tp>__int256 operator*(const _Tp& x)const
{
    __int256 ans=__int256();
    if(*this==ans||x==0)return ans;
    if(neg!=(x<0))ans.neg=1;
    ans.len=len;
    ull tmp;
    for(int i=1;i<=len;++i)
    {
        tmp=1ull*a[i]*x+ans.a[i];
        if(tmp>=base)
        {
            ans.a[i]=tmp%base;
            ans.a[i+1]+=tmp/base;
        }
        else ans.a[i]=tmp;
    }
    while(ans.a[ans.len]>0)++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;
    if(neg!=(x<0))ans.neg=1;
    for(int i=len;i;--i)
    {
        res=res*base+a[i];
        ans.a[i]=res/x;
        res%=x;
    }
    while(ans.a[ans.len]>0)++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 __int256(x);
    ull res=0;
    for(int i=len;i;--i)
    {
        res=res*base+a[i];
        res%=x;
    }
    return res;
}

最终封装版

最后简单用 class 封装了一下，利用了 template 以实现与其他类型的更高的兼容度

里面还内置一个输入输出函数，同时重载了输入输出流，非常方便

namespace cmyInteger
{
	typedef long long ll;
	typedef unsigned long long ull;
	class __int256
	{
	private:
		const static int N=2333,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)
		{
			memset(a,0,sizeof(a));
			if(x<0)x=-x,neg=1;
			len=0;
			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[i]);
				while(tmp--)putchar('0');
				write(a[i]);
			}
		}
		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[i]!=x.a[i])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[i]!=x.a[i])return a[i]>x.a[i];
			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[i]!=x.a[i])return a[i]<x.a[i];
			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[i]+=a[i]+x.a[i];
				if(ans.a[i]>=base)ans.a[i]-=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[i]+=a[i]-x.a[i];
				if(ans.a[i]<0)ans.a[i]+=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=std::max(len,x.len);
			ull tmp;
			for(int i=1;i<=len;++i)
				for(int j=1;j<=x.len;++j)
			{
				tmp=1ull*a[i]*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]>0)++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=*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=*this-__int256(x);}
		template<typename _Tp>__int256 operator-=(const _Tp& x){return *this=*this-x;}
		template<typename _Tp>__int256 operator*(const _Tp& x)const
		{
			__int256 ans=__int256();
			if(*this==ans||x==0)return ans;
			if(neg!=(x<0))ans.neg=1;
			ans.len=len;
			ull tmp;
			for(int i=1;i<=len;++i)
			{
				tmp=1ull*a[i]*x+ans.a[i];
				if(tmp>=base)
				{
					ans.a[i]=tmp%base;
					ans.a[i+1]+=tmp/base;
				}
				else ans.a[i]=tmp;
			}
			while(ans.a[ans.len]>0)++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:divide 0\n",exit(-1);
			__int256 ans=__int256();
			if(len==1&&x>a[1])return ans;
			ull res=0;
			if(neg!=(x<0))ans.neg=1;
			for(int i=len;i;--i)
			{
				res=res*base+a[i];
				ans.a[i]=res/x;
				res%=x;
			}
			while(ans.a[ans.len]>0)++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 __int256(x);
			ull res=0;
			for(int i=len;i;--i)
			{
				res=res*base+a[i];
				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 欢迎指正

博客园传送门

知乎传送门

标签：__,封装,高精度,压位,return,int256,len,ans,const
From： https://www.cnblogs.com/cmy-blog/p/gao-jing-du.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99