bignum.h

大整数问题 设n是一个k（1≤k≤80）位的十进制正整数。 问题1：对于给定的任意整数n

#include<string>

#include<cmath>

class BigNum{
public:
	vector<int> a;
	int sign;
	BigNum(){}
	BigNum(BigNum& b){
		a=vector<int>(b.a);
		sign=b.sign;
	}
	BigNum(const BigNum& b){
		a=vector<int>(b.a);
		sign=b.sign;
	}
	BigNum(vector<int>& v,int si=0){
		a=vector<int>(v);
		sign=si;
	}
	BigNum(const vector<int>& v,const int si){
		a=vector<int>(v);
		sign=si;
	}
	BigNum(char* str){
		string s(str);
		int i=0;
		sign=0;
		if (s[0]=='-') {
			sign=1;
			i=1;
		}else if (s[0]=='+'){
			i=1;
		}
		
		for ( ;i< s.size(); i++){
			a.push_back(s[i]-48);
		}
		
	}
	BigNum(string s){
		int i=0;
		sign=0;
		if (s[0]=='-') {
			sign=1;
			i=1;
		}else if (s[0]=='+'){
			i=1;
		}
		
		for ( ;i< s.size(); i++){
			a.push_back(s[i]-48);
		}
	}
	BigNum(long l){
		long r;
		long tl;
		if (l<0){
			tl=abs(l);
			sign=1;
		}else{
			tl=l;
			sign=0;
		}
		while(1){
			r=tl%10;
			a.insert(a.begin(),r);
			tl=tl/10;
			if (tl==0) break;
		}
	}
	BigNum(vector<int>& v,int si){
		a=vector<int>(v);
		sign=si;
	}
	BigNum(const vector<int>& v,const int si){
		a=vector<int>(v);
		sign=si;
	}
	BigNum& operator=(const BigNum& b){
		a=b.a;
		sign=b.sign;
		return *this;
	}
	BigNum& operator=(char* str){
		int i;
		string s(str);
		a.clear();
		sign=0;i=0;
		if (s[0]=='-') {
			sign=1;
			i=1;
		}else if (s[0]=='+'){
			i=1;
		}
		for ( ;i<s.size();i++){
			a.push_back(s[i]-48);
		}
		return *this;
	}
	int& operator[](int i){
		return a[i];
	}
	int operator[](int i) const {
		return a[i];
	}
	int size() const{
		return a.size();
	}
};
ostream& operator<<(ostream& out, const BigNum& b);
int comp(const BigNum& l,const BigNum& r){
		if (l.size()> r.size()) {
		return 1;
	} else if (l.size()< r.size()){
		return -1;
	}else {
		int i;
		for (i=0;i<l.size();i++){
			if (l[i]>r[i]) return 1; 
			else if (l[i]<r[i]) return -1;
		}
	}
	return 0;
}
BigNum& operator+(const BigNum& l,const BigNum& r){
	int carry=0;
	int i,j,k,z;
	int sign;
	int nl,nr;//两数的长度
	int ns,nb;//小数的长度与大数的长度
	int x;
	vector<int> re;
	vector<int> ds,dt;
	if (l.sign==r.sign){
	//同号相加部分
		nl=l.size();nr=r.size();
		if (nl>nr) ns=nr; else ns=nl;
		for (i=1; i<=ns; i++){

			x=carry+l.a[nl-i]+r.a[nr-i];
			carry=x/10;
			re.push_back(x%10);

		}
		if (nl > nr ){
			for ( ;i<=nl ;i++){
				re.push_back(l.a[nl-i]+carry);
				carry=0;
			}
		}else if (nr > nl){
			for ( ; i<= nr; i++){
				re.push_back(r.a[nr-i]+carry);
				carry=0;
			}
		}else if (carry!=0){
			re.push_back(carry);
			carry=0;
		}
	}
	else {
		//两数异号做相减运算部分
		vector<int> ds,dt;
		int p=comp(l,r);
		int ns,nt;
			if (p == -1) {
				ds=r.a;
				dt=l.a;
				if (l.sign==1) sign=0;
				else sign=1;
			} else if (p == 1){
				ds=l.a;
				dt=r.a;
				if (l.sign==1) sign=1;
				else sign=0;
			} else return *new BigNum("0");
			int lend=0;
			
			ns=ds.size();nt=dt.size();
			for (i=1; i<=ds.size(); i++){
				if (i > dt.size()){//较小数已经减完，剩余照搬就可
					x=ds[ns-i]-lend;
					if (x<0) {//向前借一位
						lend=1;
						x+=10;
					}else {
						lend=0;
					}
					re.push_back(x);
					continue;
				}
				x=ds[ns-i]-lend-dt[nt-i];
				if (x<0) {//向前借一位
					lend=1;
					x+=10;
				} else {
					lend=0;
				}
				
				re.push_back(x);
			}
	}
	//决定符号
	int u=comp(l,r);
		if (u == -1){
			sign=r.sign;
		}else if (u==1 ){
			sign=l.sign;
		}else sign=0;

	//倒序输出
	vector<int> tt;
	for (i=re.size()-1;i>= 0 ;i--){
		tt.push_back(re[i]);
	}

	return *new BigNum(tt,sign);
}



BigNum& operator-(const BigNum& l,const BigNum& r){
	const BigNum tb(r.a,(r.sign+1)%2);

	return l+tb;
}

BigNum& operator*(const BigNum& l,const BigNum& r){
	int nr,nl;
	int i,j,k,x,carry,sign;
	carry=0;
	vector<int> re;
	nl=l.size();nr=r.size();
	for (i=1 ;i<= nr ;i++){
		for (j=1;j<= nl ;j++){
			
			if (j+i-2== re.size()){
				
				x=r[nr-i]*l[nl-j]+carry;
				re.push_back(x%10);
				carry=x/10;
			}else{
				x=re[i+j-2]+r[nr-i]*l[nl-j]+carry;
				re[j+i-2]=x%10;
				carry=x/10;
			}
		}
		while (carry!=0) {
			if (j+i-2 <re.size()){
				x=re[j+i-2]+carry;
				re[j+i-2]=x%10;
				carry=x/10;
			}else{
				re.push_back(carry);
				carry=0;
			}
		}
	}
	
	if (l.sign == r.sign) {
		sign=0;
	}else{
		sign=1;
	}
	//倒序输出
	
	for (i=re.size()-1; i>=0 ;i--){
		if (re[i]!= 0) break;
		if (re[i]== 0) {
			if (i==0) {sign=0;break;}
			else re.pop_back();
		}
	}
	vector<int> tt;
	for (i=re.size()-1;i>= 0 ;i--){
		tt.push_back(re[i]);
	}

	return *new BigNum(tt,sign);
}
BigNum& operator/(const BigNum& l,const BigNum& r){
	vector<int> re;
	vector<int> s,a,b;
	int xp=5;
	int pn=xp<r.size()?xp:r.size();//除数可能很长,也可能很短
	int i,j,k;
	long pb=0;
	long pa=0;//判断商的临时算术数字
	for (j=0;j<pn;j++){
		pb+=r[j]*pow(10,pn-j-1);
	}

	for (i=0 ; i< l.size(); i++ ){
			if (s.size()==1 && s[0]==0 ) s.clear();
			s.push_back(l[i]);
			cout<<"s:"<<s<<endl;
		if (s.size() < r.size()) {
			
			if (re.size() !=0) re.push_back(0);
		}
		
		
		if(s.size()>=r.size()){
		
			int tre;
		
		
			pa=0;
			
			for (j=0;j<pn+s.size()-r.size();j++){
				pa+=s[j]*pow(10,pn+s.size()-r.size()-j-1);
			}
			
			if (pa/pb==0){
				if (re.size() !=0) re.push_back(0);
		
				//if (i!=l.size() && re.size() !=0) re.push_back(0);
				continue;
			//	if (i==l.size()-1) break;
			//	i++;
				
			//	s.push_back(l[i]);
			//	if (re.size() !=0) re.push_back(0);
			//	pa=pa*10+l[i-r.size()-1+xp];
			}
			tre=pa/pb;
			
			BigNum vre(BigNum(s)-(r*BigNum(vector<int>(1,tre))));
			cout<<"s : "<<s;
			cout<<"tre:  "<<tre;
			cout<<"vre:  "<<vre<<endl;
			if (vre.sign==1) {
			//	if (re.size()==1 && re[0]==0 ) re.clear();
				re.push_back(tre-1);
				s=(vre+r).a;
			}else{
			//	if (re.size()==1 && re[0]==0 ) re.clear();
				re.push_back(tre);
				s=vre.a;
			}
			cout<<"s : "<<s;
			
		}
	}//end for i

BigNum *br=new BigNum(re);
br->remain=s;
return *br;
}
bool operator<(const BigNum& l,const BigNum& r){
	if (l.sign-r.sign == 0) {
		int u=comp(l,r);
			if (u==-1) return true;
			else  return false;
	}else if (l.sign-r.sign == -2){
		int u=comp(l,r);
			if (u==-1) return false;
			else  return true;
	}else if (l.sign -r.sign ==-1){
		return false;
	}else if (l.sign- r.sign ==1){
		return true;
	}
}

ostream& operator<<(ostream& out, const BigNum& b){
	int i;
	if (b.sign==1) out<<"-";
	for (i=0;i< b.a.size();i++){
		out<<b.a[i];
	}
	
	return out;
}

void calc(char *a,char *b){
	BigNum aa(a);
	BigNum bb(b);
	cout<<aa<<" / "<<bb<<" = "<<aa/bb<<endl;
	
}