大数四则运算类

冷不防 2021-11-11 00:48 308阅读 0赞

\#include  " stdlib.h "   
\#include  < iostream >   
\#include  < assert.h >   
\#include  < time.h >   
\#include  < vector >   
 using  namespace  std;  
  
  
 \#define  BI\_NEG 0   
 \#define  BI\_POS 1   
  
 class  big\_int;  
 const  big\_int  operator \+ ( const  big\_int  & ,  const  big\_int  & );  
 const  big\_int  operator \- ( const  big\_int  & ,  const  big\_int  & );  
 const  big\_int  operator \* ( const  big\_int  & ,  const  big\_int  & );  
 const  big\_int  operator / ( const  big\_int  & ,  const  big\_int  & );  
 const  big\_int  operator % ( const  big\_int  & ,  const  big\_int  & );  
 bool  operator < ( const  big\_int  & ,  const  big\_int  & );  
 bool  operator <= ( const  big\_int  & ,  const  big\_int  & );  
 bool  operator == ( const  big\_int  & ,  const  big\_int  & );  
 bool  operator >= ( const  big\_int  & ,  const  big\_int  & );  
 bool  operator > ( const  big\_int  & ,  const  big\_int  & );  
ostream &  operator << (ostream &  \_OStr,  const  big\_int &  rhs);  
  
 const  big\_int bipow( const  big\_int  & ,  const  int );  
 const  big\_int bifact( int );  
  
  
 class  big\_int  
\{  
 private :  
 static  const  unsigned  base  =  10000 ;  
 int  sign;  
vector < unsigned >  number;  
  
 public :  
big\_int()\{number.push\_back( 0 );\};  
big\_int( const  char  \* );  
big\_int( const  big\_int  & bi):number(bi.number),sign(bi.sign)\{\};  
big\_int( int );  
big\_int( long  long );  
  
 int  get\_sign()\{  return  sign;\};  
  
big\_int &  operator \+= ( const  big\_int & );  
big\_int &  operator \-= ( const  big\_int & );  
big\_int &  operator \*= ( const  big\_int & );  
big\_int &  operator /= ( const  big\_int & );  
big\_int &  operator %= ( const  big\_int & );  
 void  output();  
 private :  
friend  bool  operator < ( const  big\_int  & ,  const  big\_int  & );  
friend ostream &  operator << (ostream & ,  const  big\_int & );  
 // number加上rhs的number   
  void  add( const  vector < unsigned >  & );  
 // 两个相减，结果放回number中   
  void  minus( const  vector < unsigned >  & ,  const  vector < unsigned >  & );  
 void  minus( const  vector < unsigned >  & );  
 static  bool  less( const  vector < unsigned >  & ,  const  vector < unsigned >  & );  
\};  
  
big\_int::big\_int( int  n)  
\{  
 if (n  <  0 ) sign  =  BI\_NEG;  else  sign  =  BI\_POS;  
 if (n  ==  0 ) \{number.push\_back( 0 );\}  
 else   
\{  
 if (n  <  0 ) n  =  \- n;  
 while (n  !=  0 )  
\{  
number.push\_back(n  %  base );  
n  /=  base ;  
\}  
\}  
\}  
big\_int::big\_int( long  long  n)  
\{  
 if (n  <  0 ) sign  =  BI\_NEG;  else  sign  =  BI\_POS;  
 if (n  ==  0 ) \{number.push\_back( 0 );\}  
 else   
\{  
 if (n  <  0 ) n  =  \- n;  
 while (n  !=  0 )  
\{  
number.push\_back(( int )(n  %  base ));  
n  /=  base ;  
\}  
\}  
\}  
  
big\_int::big\_int( const  char  \*  str)  
\{  
 int  len  =  strlen(str);  
assert(len  >  0 );  
 int  from  =  0 ;  
 int  temp  =  0 ;  
 if (str\[ 0 \]  ==  ' \- ' )\{sign  =  BI\_NEG; from  =  1 ;\}  
 else \{sign  =  BI\_POS;\}  
 int  idx  =  len  \-  1 ;  
 int  de  =  0 ;  
 int  times  =  1 ;  
 while (idx  \-  de  >=  from)  
\{  
 if (de  %  4  ==  0 )  
\{  
times  =  1 ;  
\}  
temp  \+=  (times  \*  (str\[idx  \-  de\]  \-  ' 0 ' ));  
times  \*=  10 ;  
 if (de  %  4  ==  3 )  
\{  
number.push\_back(temp);  
temp  =  0 ;  
\}  
 \++ de;  
\}  
 if (temp  !=  0 ) number.push\_back(temp);  
 int  i  =  number.size()  \-  1 ;  
 while (i  >  0  &&  number\[i\]  ==  0 )\{number.pop\_back();  \-- i;\}  
 if (number.size()  ==  0 ) \{number.push\_back( 0 );sign  =  BI\_POS;\}  
\}  
 void  big\_int::output()  
\{  
 if (sign  ==  BI\_NEG) cout  <<  ' \- ' ;  
cout  <<  number\[number.size()  \-  1 \];  
 for ( int  i  =  number.size()  \-  2 ; i  >=  0 ;  \-- i)  
\{  
cout  <<  number\[i\]  /  1000  <<  (number\[i\]  %  1000 )  /  100   
 <<  (number\[i\]  %  100 )  /  10  <<  number\[i\]  %  10 ;  
\}  
\}  
 bool  big\_int::less( const  vector < unsigned >  & lhs,  const  vector < unsigned >  & rhs)  
\{  
 if (lhs.size()  <  rhs.size())  return  true ;  
 else  if (rhs.size()  <  lhs.size())  return  false ;  
 else   
\{  
 for ( int  i  =  lhs.size()  \-  1 ; i  >=  0 ;  \-- i)  
\{  
 if (lhs\[i\]  <  rhs\[i\])  return  true ;  
 else  if (rhs\[i\]  <  lhs\[i\])  return  false ;  
\}  
\}  
 return  false ;  
\}  
  
 void  big\_int::add( const  vector < unsigned >  & rhs)  
\{  
 int  nleft  =  number.size();  
 int  nright  =  rhs.size();  
 int  i  =  0 ;  
unsigned c  =  0 ;  
unsigned temp  =  0 ;  
 while (nleft  <  nright)\{ number.push\_back( 0 );  \++ nleft;\}  
 while (i  <  nright)  
\{  
temp  =  number\[i\]  \+  rhs\[i\]  \+  c;  
number\[i\]  =  temp  %  base ;  
c  =  temp  /  base ;  
 \++ i;  
\}  
 while (i  <  nleft  &&  c  !=  0 )  
\{  
temp  =  number\[i\]  \+  c;  
number\[i\]  =  temp  %  base ;  
c  =  temp  /  base ;  
 \++ i;  
\}  
 if (c  !=  0 ) number.push\_back(c);  
\}  
  
 void  big\_int::minus( const  vector < unsigned >  & lhs,  const  vector < unsigned >  & rhs)  
\{  
vector < unsigned >  res;  
 int  nleft  =  lhs.size();  
 int  nright  =  rhs.size();  
 int  i  =  0 ;  
unsigned c  =  0 ;  
unsigned temp  =  0 ;  
res.resize(nleft);  
 for (i  =  nleft  \- 1 ; i  >=  0 ;  \-- i) res\[i\]  =  0 ;  
i  =  0 ;  
 while (i  <  nright)  
\{  
temp  =  lhs\[i\]  \+  base  \-  rhs\[i\]  \-  c;  
res\[i\]  =  temp  %  base ;  
c  =  temp  /  base ;  
c  =  (c  ==  1  ?  0  :  1 );  
 \++ i;  
\}  
 while (i  <  nleft)  
\{  
temp  =  lhs\[i\]  \+  base  \-  c;  
res\[i\]  =  temp  %  base ;  
c  =  temp  /  base ;  
c  =  (c  ==  1  ?  0  :  1 );  
 \++ i;  
\}  
i  =  nleft  \-  1 ;  
 while (i  >  0  &&  res\[i\]  ==  0 )\{ res.pop\_back();  \-- i;\}  
number  =  res;  
\}  
  
 void  big\_int::minus( const  vector < unsigned >  & rhs)  
\{  
 int  nleft  =  number.size();  
 int  nright  =  rhs.size();  
 int  i  =  0 ;  
unsigned c  =  0 ;  
unsigned temp  =  0 ;  
 while (i  <  nright)  
\{  
temp  =  number\[i\]  \+  base  \-  rhs\[i\]  \-  c;  
number\[i\]  =  temp  %  base ;  
c  =  temp  /  base ;  
c  =  (c  ==  1  ?  0  :  1 );  
 \++ i;  
\}  
 while (i  <  nleft)  
\{  
temp  =  number\[i\]  \+  base  \-  c;  
number\[i\]  =  temp  %  base ;  
c  =  temp  /  base ;  
c  =  (c  ==  1  ?  0  :  1 );  
 \++ i;  
\}  
i  =  nleft  \-  1 ;  
 while (i  >  0  &&  number\[i\]  ==  0 )\{number.pop\_back();  \-- i;\}  
\}  
  
big\_int &  big\_int:: operator \+= ( const  big\_int  & rhs)  
\{  
 if (rhs.sign  ==  sign)\{ add(rhs.number);\} // 同号相加   
  else  if (less(number, rhs.number)) // 绝对值较小   
  \{  
sign  =  rhs.sign;  
minus(rhs.number,number);  
\}  
 else   
\{  
minus(rhs.number);  
\}  
 return  \* this ;  
\}  
  
big\_int &  big\_int:: operator \-= ( const  big\_int  & rhs)  
\{  
 if (rhs.sign  !=  sign)\{ add(rhs.number);\} // 异号则相加   
  else  if (less(number, rhs.number))  
\{  
sign  =  sign  ^  1 ;  
minus(rhs.number, number);  
\}  
 else   
\{  
minus(rhs.number);  
\}  
 return  \* this ;  
\}  
big\_int &  big\_int:: operator \*= ( const  big\_int  & rhs)  
\{  
 if (sign  !=  rhs.sign) sign  =  BI\_NEG;  else  sign  =  BI\_POS;  
 int  nleft  =  number.size();  
 int  nright  =  rhs.number.size();  
 int  i,j,c,temp,idx;  
 int  maxlen  =  nleft  \+  nright  \+  1 ;  
vector < unsigned >  res;  
res.resize(maxlen);  
 for (i  =  0 ; i  <  maxlen;  \++ i)\{ res\[i\]  =  0 ;\};  
 for (i  =  0 ; i  <  nright;  \++ i)  
\{  
c  =  0 ; temp  =  0 ; idx  =  i;  
 for (j  =  0 ; j  <  nleft;  \++ j)  
\{  
temp  =  number\[j\]  \*  rhs.number\[i\]  \+  res\[idx\]  \+  c;  
res\[idx\]  =  temp  %  base ;  
c  =  temp  /  base ;  
 \++ idx;  
\}  
 while (c  !=  0 )  
\{  
temp  =  res\[idx\]  \+  c;  
res\[idx\]  =  temp  %  base ;  
c  =  temp  /  base ;  
 \++ idx;  
\}  
\}  
i  =  res.size()  \-  1 ;  
 while (i  >  0  &&  res\[i\]  ==  0 )\{res.pop\_back();  \-- i;\}  
number  =  res;  
 return  \* this ;  
\}  
  
big\_int &  big\_int:: operator /= ( const  big\_int  & rhs)  
\{  
 int  nleft  =  number.size();  
 int  nright  =  rhs.number.size();  
 int  i, temp;  
 if (sign  !=  rhs.sign) sign  =  BI\_NEG;  else  sign  =  BI\_POS;  
assert( ! (nright  ==  1  &&  rhs.number\[ 0 \]  ==  0 )); // 除数不为0   
  if (less(number,rhs.number))  
\{  
number.resize( 0 ); number.push\_back( 0 );sign  =  BI\_POS;  return  \* this ;  
\}  
vector < unsigned >  diver;  
vector < unsigned >  mid;  
vector < unsigned >  res;  
diver.resize(nright  \+  1 );  
mid.resize(nright  \+  1 );  
 for (i  =  0 ; i  <=  nright;  \++ i) diver\[i\]  =  0 ;  
res.resize(nleft  \-  nright  \+  1 );  
 for (i  =  0 ; i  <=  nleft  \-  nright;  \++ i) res\[i\]  =  0 ;  
 int  ires  =  nleft  \-  nright;  
 int  idx  =  nleft  \-  nright  \+  1 ;  
 for (i  =  0 ; i  <  nright  \-  1 ;  \++ i)  
\{  
diver\[i\]  =  number\[idx  \+  i\];  
\}  
 \-- idx;  
 int  max\_idx\_diver  =  diver.size()  \-  1 ;  
 int  max\_idx\_right  =  rhs.number.size()  \-  1 ;  
 int  temp\_res;  
 int  c, temp2;  
 for (; idx  >=  0 ;  \-- idx)  
\{  
 for (i  =  max\_idx\_diver; i  >  0 ;  \-- i) diver\[i\]  =  diver\[i \- 1 \];  
diver\[ 0 \]  =  number\[idx\];  
temp  =  diver\[max\_idx\_diver\]  \*  base  \+  diver\[max\_idx\_diver  \-  1 \];  
temp\_res  =  temp  /  rhs.number\[max\_idx\_right\];  
  
 while (temp\_res  >=  0 )  
\{  
c  =  0 ;  
 for (i  =  0 ; i  <=  max\_idx\_right;  \++ i)  
\{  
temp2  =  rhs.number\[i\]  \*  temp\_res  \+  c;  
mid\[i\]  =  temp2  %  base ;  
c  =  temp2  /  base ;  
\}  
mid\[max\_idx\_diver\]  =  c;  
 if (less(diver,mid))  \-- temp\_res;  
 else  break ;  
\}  
  
c  =  0 ;  
 for (i  =  0 ; i  <=  max\_idx\_right;  \++ i)  
\{  
temp2  =  rhs.number\[i\]  \*  temp\_res  \+  c;  
mid\[i\]  =  temp2  %  base ;  
c  =  temp2  /  base ;  
\}  
mid\[max\_idx\_diver\]  =  c;  
c  =  0 ;  
 for (i  =  0 ; i  <=  max\_idx\_diver;  \++ i)  
\{  
temp2  =  diver\[i\]  \+  base  \-  mid\[i\]  \-  c;  
diver\[i\]  =  temp2  %  base ;  
c  =  temp2  /  base ;  
c  =  c  ^  1 ;  
\}  
res\[idx\]  =  temp\_res;  
\}  
i  =  res.size()  \-  1 ;  
 while (i  >  0  &&  res\[i\]  ==  0 )\{res.pop\_back();  \-- i;\}  
number  =  res;  
 return  \* this ;  
\}  
  
  
big\_int &  big\_int:: operator %= ( const  big\_int &  rhs)  
\{  
 int  nleft  =  number.size();  
 int  nright  =  number.size();  
assert( ! (nright  ==  1  &&  rhs.number\[ 0 \]  ==  0 ));  
 // 符号不变   
  if (less(number,rhs.number))  return  \* this ;  
big\_int bi1( \* this );  
bi1  /=  rhs;  
bi1  \*=  rhs;  
big\_int bi2( \* this );  
bi2  \-=  bi1;  
number  =  bi2.number;  
 if (number.size()  ==  1  &&  number\[ 0 \]  ==  0 ) sign  =  BI\_POS;  
 return  \* this ;  
\}  
 //  
 const  big\_int  operator \+ ( const  big\_int  & lhs,  const  big\_int  & rhs)  
\{  
big\_int res(lhs);  
res  \+=  rhs;  
 return  res;  
\}  
 const  big\_int  operator \- ( const  big\_int  & lhs,  const  big\_int  & rhs)  
\{  
big\_int res(lhs);  
res  \-=  rhs;  
 return  res;  
\}  
 const  big\_int  operator \* ( const  big\_int  & lhs,  const  big\_int  & rhs)  
\{  
big\_int res(lhs);  
res  \*=  rhs;  
 return  res;  
\}  
 const  big\_int  operator / ( const  big\_int  & lhs,  const  big\_int  & rhs)  
\{  
big\_int res(lhs);  
res  /=  rhs;  
 return  res;  
\}  
 const  big\_int  operator % ( const  big\_int  & lhs,  const  big\_int  & rhs)  
\{  
big\_int res(lhs);  
res  %=  rhs;  
 return  res;  
\}  
 bool  operator < ( const  big\_int  & lhs,  const  big\_int  & rhs)  
\{  
 if (lhs.sign  <  rhs.sign)  return  true ;  
 else  if (rhs.sign  <  lhs.sign)  return  false ;  
 else  if (lhs.sign  ==  BI\_POS)  return  big\_int::less(lhs.number,rhs.number);  
 else  return  big\_int::less(rhs.number, lhs.number);  
\}  
 bool  operator <= ( const  big\_int  & lhs,  const  big\_int  & rhs)  
\{  
 return  ! (rhs  <  lhs);  
\}  
 bool  operator == ( const  big\_int  & lhs,  const  big\_int  & rhs)  
\{  
 return  ! (rhs  <  lhs)  &&  ! (lhs  <  rhs);  
\}  
 bool  operator >= ( const  big\_int  & lhs,  const  big\_int  & rhs)  
\{  
 return  ! (lhs  <  rhs);  
\}  
 bool  operator > ( const  big\_int  & lhs,  const  big\_int  & rhs)  
\{  
 return  rhs  <  lhs;  
\}  
ostream &  operator << (ostream &  \_OStr,  const  big\_int &  rhs)  
\{  
 if (rhs.sign  ==  BI\_NEG) \_OStr  <<  ' \- ' ;  
\_OStr  <<  rhs.number\[rhs.number.size()  \-  1 \];  
 for ( int  i  =  rhs.number.size()  \-  2 ; i  >=  0 ;  \-- i)  
\{  
\_OStr  <<  rhs.number\[i\]  /  1000  <<  (rhs.number\[i\]  %  1000 )  /  100   
 <<  (rhs.number\[i\]  %  100 )  /  10  <<  rhs.number\[i\]  %  10 ;  
\}  
 return  \_OStr;  
\}  
  
 const  big\_int bipow( const  big\_int  & lhs,  const  int  rhs)  
\{  
assert(rhs  >=  0 );  
big\_int res( 1 );  
 for ( int  i  =  0 ; i  <  rhs;  \++ i)  
\{  
res  \*=  lhs;  
\}  
 return  res;  
\}  
  
 const  big\_int bifact( int  n)  
\{  
big\_int res( 1 );  
 for ( int  i  =  2 ; i  <=  n;  \++ i)  
\{  
res  \*=  i;  
\}  
 return  res;  
\}

转载于:https://www.cnblogs.com/one-piece/archive/2010/05/31/1748385.html