压位高精模板

struct bignum{
	ll dat[150];
	bignum() {memset(dat,0,sizeof(dat));dat[0]=1;}
	void print(){
		printf("%ld",dat[dat[0]]);
		for(register int i=dat[0]-1;i>=1;--i)
			printf("%04ld",dat[i]);
	}
	bool operator ==(const bignum &a)const{
		for(register int i=0;i<=dat[0];++i)
			if(dat[i]!=a.dat[i])
				return false;
		return true;
	}
	bool operator <(const bignum &a)const{
		if(dat[0]>a.dat[0]) return false;
		if((*this)==a) return false;
		if(dat[0]<a.dat[0]) return true;
		for(register int i=dat[0];i>=1;--i){
			if(dat[i]>a.dat[i]) return false;
			if(dat[i]<a.dat[i]) return true;
		}
		return true;
	}
	bignum operator *(const int &a)const{
        bignum tmp;
        tmp.dat[0]=dat[0];
        int laz=0;
        for(register int i=1;i<=tmp.dat[0];++i){
            tmp.dat[i]=dat[i]*a+laz;
            laz=tmp.dat[i]/base;
            tmp.dat[i]=tmp.dat[i]%base;
        }
        for(;laz;){
            tmp.dat[++tmp.dat[0]]=laz%base;
            laz/=base;
        }
        for(;!tmp.dat[tmp.dat[0]]&&tmp.dat[0]>1;) tmp.dat[0]--;
        return tmp;
    }
    bignum operator /(const int &a)const{
    	bignum tmp;
    	tmp.dat[0]=dat[0];
    	int laz=0;
    	for(register int i=tmp.dat[0];i>=1;--i){
    		tmp.dat[i]=(laz*base+dat[i])/a;
    		laz=(laz*base+dat[i])%a;
		}
		for(;!tmp.dat[tmp.dat[0]]&&tmp.dat[0]>1;) tmp.dat[0]--;
		return tmp;
	}
	bignum operator +(const bignum &a)const{
		bignum tmp;
		tmp.dat[0]=max(a.dat[0],dat[0]);
		for(register int i=1;i<=tmp.dat[0];++i){
			tmp.dat[i]+=dat[i]+a.dat[i];
			tmp.dat[i+1]+=tmp.dat[i]/base;
			tmp.dat[i]%=base;
		}
		if(tmp.dat[tmp.dat[0]+1]) tmp.dat[0]++;
		return tmp;
	}
	bignum operator -(const bignum &a)const{
		bignum tmp;
		tmp.dat[0]=dat[0];
		int tag=0;
		for(register int i=1;i<=dat[0];++i){
			tmp.dat[i]=dat[i]-a.dat[i]-tag;
			if(tmp.dat[i]<0){
				tmp.dat[i]+=base;
				tag=1;
			}
			else tag=0;
		}
		for(;!tmp.dat[tmp.dat[0]]&&tmp.dat[0]>1;) tmp.dat[0]--;
		return tmp;
	}
	bignum operator *(const bignum &a)const{
		bignum tmp;
		int len=dat[0]+a.dat[0];
		for(register int i=1;i<=dat[0];++i)
			for(register int j=1;j<=a.dat[0];++j){
				tmp.dat[i+j-1]+=dat[i]*a.dat[j];
				tmp.dat[i+j]+=tmp.dat[i+j-1]/base;
				tmp.dat[i+j-1]=tmp.dat[i+j-1]%base;
			}
		for(;!tmp.dat[len]&&len>1;) --len;
		tmp.dat[0]=len;
		return tmp;
	}
	bignum operator /(const bignum &a)const{
		bignum tmp1,tmp2;
		int len=dat[0];
		for(register int i=dat[0];i>=1;--i){
			tmp1=tmp1*base;
			tmp1.dat[1]=dat[i];
			int cnt=0;
			while(a<tmp1||tmp1==a){
				cnt++;
				tmp1=tmp1-a;
			}
			tmp2.dat[i]=cnt;
		}
		while(!tmp2.dat[len]&&len>1) --len;
		tmp2.dat[0]=len;
		return tmp2;
	}
	bignum operator % (const bignum &a)const{
		bignum tmp;
		if((*this)<a) return (*this);
		int len=dat[0];
		for(register int i=len;i>=1;--i){
			tmp=tmp*base;
			tmp.dat[1]=dat[i];
			while(a<tmp||tmp==a)
				tmp=tmp-a;
		}
		for(;!tmp.dat[len]&&len>1;) --len;
		tmp.dat[0]=len;
		return tmp;
	}
};