高精度模板第一次修订版

把之前自己用的大数板子升级了一下：

更新记录：

1 增加了读入函数，修正输出时的bug。

2 增加了更多的大小关系判断，可以直接用 sort 函数排序了。

3 从以前用 long long 存储7位变成用 int 存储4位，对各oj泛用性更好

4 增加了对int数取模

5 去掉了从 64位整数读入

6 代码风格和细节优化

以下摘录几个别人的模板，备用。

hdu 4002 收获非常大的一个题 多功能大数模板的应用

一个非常好用的大数类模板BigNum.

HDU 1134 大数取模 使用大数模板

#include <cmath>
#include <stack>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MOD=10000;   //数组每个元素保存4位数字
const int maxlen=1000+20;  //数字最长位数

class BigNum
{
private:
	int a[maxlen/4+5];

public:
	BigNum operator + (BigNum temp)  //大数+大数
	{
		BigNum ans;
		int i,j,k,p;
		if (a[0]>temp.a[0]) p=a[0];
		else p=temp.a[0];
			
		for (i=a[0],j=temp.a[0],k=p; j>=1&&i>=1; i--,j--,k--)
			ans.a[k]=a[i]+temp.a[j];
		if (j==0)
			while(i>=1) ans.a[i]=a[i--];
		else
			while(j>=1) ans.a[j]=temp.a[j--];
		
		ans.a[0]=0;
		for (i=p;i>=1;i--)
		{
			ans.a[i-1]+=ans.a[i]/MOD;
			ans.a[i]%=MOD;
		}
		if (ans.a[0])
		{
			for (i=p+1;i>=1;i--)
				ans.a[i]=ans.a[i-1];
			ans.a[0]=p+1;
		}
		else ans.a[0]=p;
		return ans;
	}
	
	BigNum operator-(BigNum temp)   //大数-大数
	{
		BigNum ans;
		int i,j;
		for (i=0;i<=a[0];i++) ans.a[i]=a[i];
		for (i=ans.a[0],j=temp.a[0];i>=1&&j>=1;i--,j--)
			ans.a[i]-=temp.a[j];
		for (i=ans.a[0];i>=1;i--) if(ans.a[i]<0)
		{
			ans.a[i]+=MOD;
			ans.a[i-1]--;
		}
		for (i=1;i<=a[0];i++) if(ans.a[i]) break;
		if (i>a[0])
		{
			ans.a[0]=1;
			ans.a[1]=0;
			return ans;
		}
		for (j=i;j<=a[0];j++) ans.a[j+1-i]=ans.a[j];
		ans.a[0]=a[0]-i+1;
		return ans;
	}
	
	BigNum operator*(BigNum temp)    //大数乘大数
	{
		BigNum ans;
		int i,p=a[0]+temp.a[0]-1;
		memset(ans.a,sizeof(ans.a));
		for (i=a[0];i>=1;i--) for (j=temp.a[0];j>=1;j--)
			ans.a[i+j-1]+=a[i]*temp.a[j];
		ans.a[0]=0;
		for (i=p;i>=1;i--)
		{
			ans.a[i-1]+=ans.a[i]/MOD;
			ans.a[i]%=MOD;
		}
		if (ans.a[0])
		{
			for (i=p;i>=0;i--) ans.a[i+1]=ans.a[i];
			ans.a[0]=p+1;
		}
		else ans.a[0]=p;
		return ans;
	}
	
	BigNum operator*(int temp)  //大数乘以小数
	{
		BigNum ans;
		int i;
		for (i=1;i<=a[0];i++) ans.a[i]=a[i]*temp;
		ans.a[0]=0;
		for (i=a[0];i>=1;i--)
		{
			ans.a[i-1]+=ans.a[i]/MOD;
			ans.a[i]%=MOD;
		}
		if (ans.a[0])
		{
			for (i=a[0];i>=0;i--) ans.a[i+1]=ans.a[i];
			ans.a[0]=a[0]+1;
		}
		else ans.a[0]=a[0];
		if (ans.a[1]>=MOD)
		{
			for (i=ans.a[0];i>=0;i--) ans.a[i+1]=ans.a[i];
			ans.a[0]++;
		}
		return ans;
	}
	
	BigNum operator/(int x)    //大数除以小数
	{
		BigNum ans;
		int i,p;
		for (i=1;i<=a[0];i++)
			if (i==1)
			{
				ans.a[i]=a[i]/x;
				p=a[i]%x;
			}
			else
			{
				ans.a[i]=(p*MOD+a[i])/x;
				p=(p*MOD+a[i])%x;
			}
         for (i=1;i<=a[0];i++) if(ans.a[i]) break;
		 if (i>a[0])
		 {
             ans.a[0]=1;
             ans.a[1]=0;
             return ans;
         }
		 for (j=i;j<=a[0];j++) ans.a[j+1-i]=ans.a[j];
		 ans.a[0]=a[0]-i+1;
		 return ans;
	}
	
	BigNum operator/(BigNum temp)   //大数除以大数
	{
		BigNum ans,t;
		BigNum low=BigNum(1),high,mid;
		for (int i=1;i<=a[0];i++) t.a[i]=high.a[i]=a[i];
		t.a[0]=high.a[0]=a[0];
		while (!(low>high))
		{
			mid=(low+high)/2;
			if (mid*temp>t) high=mid-BigNum(1);
			else low=mid+BigNum(1);
		}
		if (!(low>t)&&!(temp*low>t)) return low;
		return high;
	}
	
	BigNum operator%(BigNum temp)   //大数模大数
	{
		BigNum t;
		for (int i=1;i<=a[0];i++) t.a[i]=a[i];
		t.a[0]=a[0];
		return t-t/temp*temp;
	}

	int operator%(int temp)   //大数模小数
	{
		int i,d=0;
		for (i=1;i<=a[0];i++)
			d=((d*MOD)%temp+a[i])%temp;
		return d;
	}
	
	bool operator==(BigNum temp)   //大数与大数相等
	{
		if (a[0]!=temp.a[0]) return false;
		for (int i=1;i<=a[0];i++) if(a[i]!=temp.a[i]) return false;
		return true;
	}

	bool operator!=(BigNum temp)  //不等于
	{
		return !(*this==temp);
	}
	
	bool operator>(BigNum temp)   //大于比较
	{
		if (a[0]>temp.a[0]) return true;
		if (a[0]<temp.a[0]) return false;
		for (int i=1;i<=a[0];i++) if(a[i]!=temp.a[i]) return a[i]>temp.a[i];
		return false;
	}

	bool operator>=(BigNum temp)  //大于等于比较
	{
		return *this>temp || *this==temp;
	}

	bool operator<=(BigNum temp)  //小于等于比较
	{
		return !(*this>temp);
	}

	bool operator<(BigNum temp)  //小于比较
	{
		return *this<=temp && *this!=temp;
	}

public:
	BigNum ()   { memset(a,sizeof(a));a[0]=1,a[1]=0; }

	BigNum (int x)
	{
		if (x>=MOD) a[0]=2,a[1]=x/MOD,a[2]=x%MOD;
		else a[0]=1,a[1]=x;
	}

	BigNum (string str)
	{
		int i;
		for (i=0;i<str.length();i++) if(str[i]!='0') break;
		if (i==str.length())
		{
			a[0]=1,a[1]=0;
			return;
		}
		str=str.substr(i,str.length()-i);
		int p=str.length()%4,k;
		a[0]=0;
		if (p)
		{
			a[0]=1,k=0;
			for (i=0;i<p;i++) k=k*10+str[i]-'0';
			a[1]=k;
			str=str.substr(p,str.length()-p);
		}
		for (i=0;i<str.length();)
		{
			k=0;
			for (j=i;j<i+4;j++) k=k*10+str[j]-'0';
			a[++a[0]]=k;
			i=j;
		}
	}

	int scan ()
	{
		string str;		
		if (cin >>str) { *this=str;return 1; }
		return -1;
	}
	
	void print ()
	{
		printf("%d",a[1]);
		for (int i=2;i<=a[0];i++) printf("%04d",a[i]);
	}
};