Beyond the Void
BYVoid
高精度计算对象

高精度加、减、单乘、双乘、比较大小、读入、输出

#include <iostream>

using namespace std;

template<int LIM,int MAX> class hp
{
	public:
		//vars
		int sect[MAX];
		int scnt;
		//constructors
		hp()
		{
			scnt=1;
			sect[0]=0;
		}
		//functions
		void copy(const hp<LIM,MAX> &A)
		{
			for (int i=0;i<A.scnt;i++)
				sect[i]=A.sect[i];
			scnt=A.scnt;
		}
		void copy(int A)
		{
			scnt=0;
			while (A)
			{
				sect[scnt++]=A % LIM;
				A /=LIM;
			}
		}
		void print()
		{
			int i,k;
			printf("%d",sect[scnt-1]);
			for (i=scnt-2;i>=0;i--)
			{
				k=LIM/10;
				while(sect[i]<k)
				{
					printf("0");
					k/=10;
				}
				if (sect[i])
					printf("%d",sect[i]);
			}
		}
		void read(int LIE)
		{
			char A[LIM*MAX];
			int len,i,j,k,b=0;
			scanf("%s",A);
			len=strlen(A);
			k=len % LIE;
			j=scnt=len / LIE;
			if (k)
			{
				scnt++;
				j=scnt-1;
				sect[j]=0;
				for (i=0;i<k;i++)
				{
					sect[j]*=10;
					sect[j]+=A[b++]-'0';
				}
			}
			for (j--;j>=0;j--)
			{
				sect[j]=0;
				for (i=0;i<LIE;i++)
				{
					sect[j]*=10;
					sect[j]+=A[b++]-'0';
				}
			}
		}
		void plus(hp<LIM,MAX> &A,int offset=0)
		{
			int sc=scnt > A.scnt + offset  ? scnt : A.scnt + offset;
			int i,j,up=0;
			for (i=0;i<sc;i++)
			{
				j=i - offset;
				if (j<0) continue;
				if (i>=scnt) sect[i]=0;
				if (j>=A.scnt) A.sect[j]=0;
				sect[i]+=A.sect[j] + up;
				up=sect[i] / LIM;
				sect[i]%=LIM;
			}
			scnt=sc;
			if (up) sect[scnt++]=up;
		}
		void minus(hp<LIM,MAX> &A)
		{
			int sc=scnt;
			int i,lend=0;
			for (i=0;i<sc;i++)
			{
				if (i>=A.scnt) A.sect[i]=0;
				sect[i]-=A.sect[i] + lend;
				lend=0;
				if (sect[i]<0)
				{
					lend=1;
					sect[i]+=LIM;
				}
			}
			scnt=sc;
			if (lend) scnt--;
			for (;scnt>1 && sect[scnt-1]==0;scnt--);

		}
		void multiply(int p)
		{
			if (p==0)
			{
				scnt=1;
				sect[0]=0;
				return;
			}
			int sc=scnt;
			int i,up=0;
			for (i=0;i<sc;i++)
			{
				if (i>=scnt) sect[i]=0;
				sect[i]=sect[i] * p + up;
				up=sect[i] / LIM;
				sect[i]%=LIM;
			}
			scnt=sc;
			if (up) sect[scnt++]=up;
		}
		void multiply(hp<LIM,MAX> &A)
		{
			hp<LIM,MAX> T,C;
			int sc=A.scnt;
			int i;
			for (i=0;i<sc;i++)
			{
				T=(*this);
				T.multiply(A.sect[i]);
				C.plus(T,i);
			}
			scnt=sc;
			(*this)=C;
		}
		int compare(hp<LIM,MAX> &A)
		{
			if (scnt > A.scnt)
				return 1;
			if (scnt < A.scnt)
				return -1;
			for (int i=scnt-1;i>=0;i--)
			{
				if (sect[i] > A.sect[i])
					return 1;
				if (sect[i] < A.sect[i])
					return -1;
			}
			return 0;
		}
		//operators
		bool operator == (hp<LIM,MAX> &A)
		{
			int t=compare(A);
			return t==0;
		}
		bool operator < (hp<LIM,MAX> &A)
		{
			int t=compare(A);
			return t==-1;
		}
		bool operator > (hp<LIM,MAX> &A)
		{
			int t=compare(A);
			return t==1;
		}
		bool operator <= (hp<LIM,MAX> &A)
		{
			int t=compare(A);
			return t==-1 || t==0;
		}
		bool operator >= (hp<LIM,MAX> &A)
		{
			int t=compare(A);
			return t==1 || t==0;
		}
		void operator =(hp<LIM,MAX> A)
		{
			copy(A);
		}
		void operator =(int A)
		{
			copy(A);
		}
		void operator +=(hp<LIM,MAX> &A)
		{
			plus(A);
		}
		void operator -=(hp<LIM,MAX> &A)
		{
			minus(A);
		}
		void operator *=(hp<LIM,MAX> &A)
		{
			multiply(A);
		}
		void operator *=(int A)
		{
			multiply(A);
		}
		hp<LIM,MAX> operator +(hp<LIM,MAX> &A)
		{
			hp<LIM,MAX> C(*this);
			C.plus(A);
			return C;
		}
		hp<LIM,MAX> operator -(hp<LIM,MAX> &A)
		{
			hp<LIM,MAX> C(*this);
			C.minus(A);
			return C;
		}
		hp<LIM,MAX> operator *(int A)
		{
			hp<LIM,MAX> C(*this);
			C.multiply(A);
			return C;
		}
		hp<LIM,MAX> operator *(hp<LIM,MAX> &A)
		{
			hp<LIM,MAX> C(*this);
			C.multiply(A);
			return C;
		}
};

typedef hp<10000,100> hpnum;

hpnum A,B;

hpnum qp(int P)
{
	hpnum A;
	if (P/2==1)
		A=2;
	else
		A=qp(P/2);
	A*=A;
	if (P%2==1)
		A*=2;
	return A;
}

void mason()
{
	int P;
	B=1;
	freopen("mason.in","r",stdin);
	freopen("mason.out","w",stdout);
	scanf("%d",&P);
	A=qp(P);
	A-=B;
	A.print();
}

void mul()
{
	char c;
	hpnum A,B,C;
	freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
	A.read(4);
	while ((c=getchar())==10 || c==13);
	ungetc(c,stdin);
	B.read(4);
	C=A*B;
	C+=B;
	C.print();
}

int main()
{
	//mason();麦森数
	//mul();高精度乘法例子
	return 0;
}

上次修改时间 2017-02-03

相关日志