eee.h

大数类

#include<iostream.h>

template<class T>
class Array
{
	public:
		Array(int size=0);
		~Array(){delete [] element;}
		int Creat();
		void Print(Array<T>& x);
		int Copy(Array<T>& x);
		void Delete(){delete [] element;}
		void Add(const Array<T>& a,const Array<T>& b,Array<T>& c);
		void Sub1(Array<T>& a,Array<T>& b,Array<T>& c);
		void Sub(Array<T>& a,Array<T>& b,Array<T>& c);
		void CF(Array<T>& a,Array<T>& b,Array<T>& c);
		int Compare(Array<T>& a,Array<T>& b);
		T& operator[](int i) const;
		int Size() const {return size;}
		int length;
	private:
		int size;
		T *element;
};

template<class T>
Array<T>::Array(int sz)
{
//	if(sz<0) throw BadInitializers();
	size=sz;
	element=new T[sz];
}

template<class T>
T& Array<T>::operator[](int i) const
{
//	if(i<0||i>=size) throw OutOfBounds();
	return element[i];
}

template<class T>
int Array<T>::Creat()
{
	for(int i=0;i<=Size();i++)
	{
		if((element[i]=getchar())=='\n')
		{
			length=i-1;
			while(i<Size())
			{
				element[i]=0;
				i++;
			}
			return 0;
		}
		else element[i]=element[i]-48;
	}
}

template<class T>
int Array<T>::Copy(Array<T>& x)
{
	int l=x.length;
	int s=x.Size()-1;
	for(int i=s;i>=0;i--)
	{
		if(l>=0)
		{
			x[i]=x[l];
			if(i!=l)
			{
				x[l]=0;
				l--;
			}
			else l--;
		}
		else return 0;
	}
}

template<class T>
void PutIn(Array<T>& a,Array<T>& b)
{
	a.Creat();
	a.Copy(a);
	b.Creat();
	b.Copy(b);
}

template<class T>
void Print(Array<T>& y)
{
	int i=0;
	for(;i<y.Size();i++)
		if(y[i]!=0) break;
	for(int j=i;j<y.Size();j++)
		cout<<y[j];
	cout<<endl;
}

template<class T>
void Array<T>::Add(const Array<T>& a,const Array<T>& b,Array<T>& c)
{
	int f=a.size-1;
	T u=a.element[f]+b.element[f];
	if(u>=10) c.element[f]=u-10;
	else c.element[f]=u;
	int r=0;
	for(int i=f;i>0;i--)
	{
		T x=a.element[i]+b.element[i]+r;
		if(x>=10) r=1;
		else r=0;
		T y=a.element[i-1]+b.element[i-1]+r;
		if(y>=10) c.element[i-1]=y-10;
		else c.element[i-1]=y;
	}
}

template<class T>
void Array<T>::Sub1(Array<T>& a,Array<T>& b,Array<T>& c)
{
	int f=a.size-1;
	T u=a.element[f]-b.element[f];
	if(u<0) c.element[f]=u+10;
	else c.element[f]=u;
	int r=0;
	for(int i=f;i>=0;i--)
	{
		T x=a.element[i]-b.element[i]-r;
		if(x<0) r=1;
		else r=0;
		T y=a.element[i-1]-b.element[i-1]-r;
		if(y<0) c.element[i-1]=y+10;
		else c.element[i-1]=y;
	}
}

template<class T>
int Array<T>::Compare(Array<T>& a,Array<T>& b)
{
	int s=a.length;
	int t=b.length;
	int m=a.size-a.length-1;
	int q=a.size;
	int j=m;
	if(s==t)
	{
		for(;j<a.size;)
		{
			if(a.element[j]==b.element[j]) {j++;q++;}
			else
			{
				if(j==a.size) break;
				else
					if(a.element[j]>b.element[j]){q=1;break;}
					else {q=-1;break;}			
			}
		}
	}
	else
	{
		if(s<t) q=-2;
		else q=2;
	}
	return q;	
}

template<class T>
void Array<T>::Sub(Array<T>& a,Array<T>& b,Array<T>& c)
{
	int p=a.size+a.length+1;
	int q=c.Compare(a,b);
	if(q==p)
	{
		c.Sub1(a,b,c);
		cout<<0;
	}
	else
	{
		if(q==1||q==2)
		c.Sub1(a,b,c);
		if(q==-1||q==-2)
		{
			Array<T> d(a.size);
			for(int i=0;i<a.size;i++)
			{
				d[i]=a[i];
				a[i]=b[i];
				b[i]=d[i];
			}
			cout<<'-';
			c.Sub1(a,b,c);
		}
	}
}
	///要考虑位数一样且第一个相同的

template<class T>
void Array<T>::CF(Array<T>& a,Array<T>& b,Array<T>& c)
{
	int f=a.size-1;
	Array<T> d(a.size),e(size);
	for(int m=0;m<a.size;m++)
		d.element[m]=0;
	int j=f;
	int q=0;
	do
	{
		T u=a.element[f]*b.element[j];
		if(u>=10) c.element[f]=u%10;
		else c.element[f]=u;
		int r=0;
		for(int i=f;i>0;i--)
		{
			T x=a.element[i]*b.element[j]+r;
			if(x>=10) r=(x-x%10)/10;
			else r=0;
			T y=a.element[i-1]*b.element[j]+r;
			if(y>=10) c.element[i-1]=y%10;
			else c.element[i-1]=y;
		}
		j--;
		Array<T> t(a.size);
		for(int l=0;l<=f;l++)
			t.element[l]=c.element[l];
		if(q!=0)
		{
			for(int z=a.size-q;z<=f;z++)
				c.element[z]=0;
			int v=0;
			for(int h=0;h<a.size-q;h++)
			{
				c.element[h]=t[v+q];
				v++;
			}
		}
		e.Add(c,d,e);
		for(int w=0;w<a.size;w++)
			d.element[w]=e.element[w];
		q++;
	}while(j>=0);
	for(int n=0;n<a.size;n++)
		c.element[n]=e.element[n];
}