大整数相关操作

大整数定义：

struct bign{
	int d[1000];
	int len;
	bign(){
		memset(d,0,sizeof(d));
		len=0;
	}
};

大整数转化：

bign change(char str[]){
	bign a;
	a.len=strlen(str);
	for(int i=0;i<a.len;i++){
		a.d[i]=str[a.len-1-i]-'0';
	}
	return a;
}

大整数比较：

//a>b:1   a<b:-1  a==b:0
bool compareBign(bign a,bign b){
	if(a.len>b.len)return 1;
	else if(a.len<b.len)return -1;
	else{
		for(int i=a.len-1;i>=0;i--){
			if(a.d[i]>b.d[i])return 1;
			else if(a.d[i]<b.d[i])return -1;
		}
		return 0;
	}
}

大整数加法：

bign add(bign a,bign b){
	bign c;
	int carry=0;
	for(int i=0;i<a.len||i<b.len;i++){
		int temp=a.d[i]+b.d[i]+carry;
		c.d[c.len++]=temp%10;
		carry=temp/10;
	}
	if(carry!=0){
		c.d[c.len++]=carry;
	}
	return c;
}

大整数减法：

bign sub(bign a,bign b){
	bign c;
	for(int i=0;i<a.len||i<b.len;i++){
		if(a.d[i]<b.d[i]){//不够减从高位借 
			a.d[i+1]--;
			a.d[i]+=10;
		}
		c.d[c.len++]=a.d[i]-b.d[i]; 
	}
	//去除高位的0，并保证最少一位数 
	while(c.len>1&&c.d[c.len-1]==0){
		c.len--;
	}
	return c;
}

大整数与整数乘法：

bign multi(bign a,int b){
	bign c;
	int carry=0;
	for(int i=0;i<a.len;i++){
		int temp=a.d[i]*b+carry;
		c.d[c.len++]=temp%10;
		carry=temp/10;
	}
	while(carry!=0){
		c.d[c.len++]=carry%10;
		carry/=10;
	}
	return c;
}

大整数与整数除法：

//r为余数
bign divide(bign a,int b,int& r){
	bign c;
	c.len=a.len;
	for(int i=a.len-1;i>=0;i--){
		r=r*10+a.d[i];
		if(r<b)c.d[i]=0;//不够除 
		else{
			a.d[i]=r/b;
			r=r%b; 
		}
	}
    //去除高位的0,并保证最少有一位数
	while(c.len>1&&c.d[c.len-1]==0){
		c.len--;
	}
	return c;
}