hp.cpp

HIgh precision 高精度代码

#include <stdio.h>
#include <string.h>

const int maxl = 3000;
const int Unit = 10000;
const int UnitSize = 4;
const int e10[5] = { 1,10,100,1000,10000 };

char str[maxl+10];int slen;
int t[maxl],tlen;
inline int max(int a,int b) { return a>b?a:b; }

struct bignum {
	int data[maxl],len;
	bignum() { memset(data,0,sizeof(data)); len=1; }	//very important in div
	void readin() {
		scanf("%s",&str);
		slen=strlen(str);
		len=0;
		memset(data, 0, sizeof(data));
		for (int i=slen-1,j=0;i>=0;i--,j++) {
			if (j%UnitSize==0) len++;
			data[len]+=(str[i]-'0')*e10[j%UnitSize];
		}
		if (len==0) len=1;
	}
	void operator = (int x) {
		memset(data,0,sizeof(data));
		len=0;
		while (x) {
			data[++len]=x%Unit;
			x/=Unit;
		}
		if (len==0) len=1;
	}
	void operator += (const bignum& b) {
		len=max(len,b.len);
		for (int i=1;i<=len;i++) {
			data[i]+=b.data[i];
			if (data[i]>=Unit) {
				data[i+1]++;
				data[i]-=Unit;
			}
		}
		if (data[len+1]) len++;
	}
	void operator -= (const bignum& b) {
		len=max(len,b.len);
		for (int i=1;i<=len;i++) {
			data[i]-=b.data[i];
			if (data[i]<0) {
				data[i+1]--;
				data[i]+=Unit;
			}
		}
		while (len>1&&data[len]==0) len--;
	}

	void mul_onedigit() {
		if (len==1&&data[len]==0) return;
		for (int i=len+1;i>1;i--) data[i]=data[i-1];
		len++;
	}
	
	void operator *= (int a) {
		if (a==0) {	*this=0;return; }
		for (int i=1;i<=len;i++) { t[i]=data[i];data[i]=0; }

		for (int i=1;i<=len;i++) {	//超出len的进位先不管
			data[i]+=t[i]*a;
			if (data[i]>=Unit) {
				data[i+1]+=data[i]/Unit;
				data[i]%=Unit;
			}
		}
		while (data[len+1]>0) {
			len++;
			if (data[len]>=Unit) {
				data[len+1]+=data[len]/Unit;
				data[len]%=Unit;
			}
		}
	}

	void operator *= (const bignum& b) {
		for (int i=1;i<=len;i++) {	t[i]=data[i];data[i]=0; }
		tlen=len;
		int w;
		for (int i=1;i<=tlen;i++)
			for (int j=1;j<=b.len;j++) {
				w=i+j-1;
				data[w]+=t[i]*b.data[j];
				if (data[w]>=Unit) {
					data[w+1]+=data[w]/Unit;
					data[w]%=Unit;
				}
			}
		len=tlen+b.len-1;
		while (data[len+1]>0) {
			len++;
			if (data[len]>=Unit) {
				data[len+1]+=data[len]/Unit;
				data[len]%=Unit;
			}
		}
	}
	
	void operator /= (int d) {
		int remain=0;
		for (int i=len;i>=1;i--) { t[i]=data[i];data[i]=0; }
		for (int i=len;i>=1;i--) {
			remain=remain*Unit+data[i];
			data[i]=remain/d;
			remain%=d;
		}
		while (len>1&&data[len]==0) len--;
	}
	void operator /= (const bignum& b);
	void dump() {
		printf("%d",data[len]);
		for (int i=len-1;i>=1;i--)
			printf("%04d",data[i]);
		printf("\n");
	}
};


bool operator < (const bignum& a,const bignum& b) {
	if (a.len<b.len) return 1;
	if (a.len>b.len) return 0;
	for (int i=a.len;i>=1;i--) {
		if (a.data[i]<b.data[i]) return 1;
		if (a.data[i]>b.data[i]) return 0;
	}
	return 0;
}

bool operator > (const bignum& a,const bignum& b) {
	if (a.len>b.len) return 1;
	if (a.len<b.len) return 0;
	for (int i=a.len;i>=1;i--) {
		if (a.data[i]>b.data[i]) return 1;
		if (a.data[i]<b.data[i]) return 0;
	}
	return 0;
}

bignum operator + (bignum a,bignum b) {
	a+=b;
	return a;
}

bignum operator - (bignum a,bignum b) {
	a-=b;
	return a;
}

bignum operator * (bignum a,int b) {
	a*=b;
	return a;
}
bignum operator * (bignum a,bignum b) {
	a*=b;
	return a;
}

bignum operator / (bignum a,int b) {
	a/=b;
	return a;
}

	void bignum::operator /= (const bignum& b) {
		for (int i=1;i<=len;i++) { t[i]=data[i];data[i]=0; }
		bignum tmp,st;
		for (int i=len;i>=1;i--) {
			tmp.mul_onedigit();
			tmp.data[1]=t[i];
			int c=0,m;
			for (int l=0,r=Unit-1;l<=r;) {
				m=(l+r)/2;
				st=b*m;
				if (!(st>tmp)) { c>?=m;l=m+1; } else r=m-1;
			}
			tmp-=b*c;
			data[i]=c;
		}
		while (len>1&&data[len]==0) len--;
	}

bignum operator / (bignum a,bignum b) {
	a/=b;
	return a;
}

int operator % (const bignum& a,int b) {
	int ret=0;
	for (int i=a.len;i>=1;i--)
		ret=(ret*Unit+a.data[i])%b;
	return ret;
}

bignum operator % (bignum a,bignum b) {
	bignum c;
	c=a/b;
	c*=b;
	a-=c;
	return a;
}

int main() {
	return 0;
}