경시대회준비반/BigInteger

About

C++ 용 BigInteger 클래스로 거의 모든 연산을 지원한다. UVA 사이트의 구식(?) 컴파일러에도 문제없이 통과할 뿐 아니라, 성능또한 훌륭하다. 고정도 정수 연산을 하는 문제의 경우, 고정도 연산을 하는 라이브러리를 본인이 직접 짜거나, 이 클래스를 이용하면 된다. 몇 일동안 삽질한 결과 후자가 낫다는 판단이 선다. 되게 잘 짜여진 코드다. 시간 내서 분석해봐야 겠다.

Code

/** 
* BigInteger Class 
* Version 6.7.25 
* 
* Copyright (c) 2001 
* Mahbub Murshed Suman (suman@bttb.net.bd) 
* 
* Permission to use, copy, modify, distribute and sell this software 
* and its documentation for any purpose is hereby granted without fee, 
* provided that the above copyright notice appear in all copies and 
* that both that copyright notice and this permission notice appear 
* in supporting documentation. Mahbub Murshed Suman makes no 
* representations about the suitability of this software for any 
* purpose. It is provided "as is" without express or implied warranty. 
*/ 
#include <iostream> 
#include <cstdlib> 
#include <cstdio> 
#include <cctype> 
#include <malloc.h> 
#include <cmath> 
#include <cstring> 
#include <ctime> 
#include <strstream> 
#include <string> 
#include <stdexcept> 

using namespace std; 

namespace BigMath 
{ 
	enum BigMathERROR { BigMathMEM = 1 , BigMathOVERFLOW , BigMathUNDERFLOW, BigMathINVALIDINTEGER, BigMathDIVIDEBYZERO,BigMathDomain}; 
	
	const char *BigIntErrDes[] = { "Allocation Failed", "Overflow","Underflow", "Invalid Integer", "Divide by Zero" ,"Domain Error"}; 
	const char BigIntPROGRAMNAME[] = { "BigInteger" }; 
	const int BigIntMajorVersion = 6; 
	const int BigIntMinorVersion = 7; 
	const int BigIntRevision = 25; 
	
	void Dump(const char *,enum BigMathERROR); 
	string& DumpString (char const*,enum BigMathERROR); 
	
	// The Size Type 
	typedef unsigned int SizeT; 
	// The Data Type 
	typedef unsigned int DATATYPE; 
	
	// The Base Used 
	const DATATYPE BASE = 10000; 
	// An invalid data 
	const DATATYPE INVALIDDATA = 65535U; 
	// Number of digits in `BASE' 
	const SizeT LOG10BASE = 4; 
	class BigInteger 
	{ 
	private: 
		// The integer array to hold the number 
		DATATYPE *TheNumber; 
		// Start of the location of the number in the array 
		SizeT Start; 
		// End of the location of the number in the array 
		SizeT End; 
		// True if the number is negative 
		bool isNegative; 
		
		// Constructor with specified bytes 
		BigInteger(SizeT,DATATYPE,bool); 
		
		// Copies data to 'this' upto size bytes 
		void datacopy(BigInteger const&,SizeT); 
		
		// Determines valid data range 
		SizeT datalen(DATATYPE const*) const; 
		// deallocates the array 
		void deallocateBigInteger(); 
		// Trims zeros in front of a number 
		void TrimZeros(); 
		// the array with the `fill' value 
		void Set(DATATYPE); 
		
	public: 
		// Default Constructor 
		BigInteger(); 
		// Long integer constructor 
		BigInteger(long); 
		// Character array constructor 
		BigInteger(char const*); 
		// Copy Constructor 
		BigInteger(BigInteger const&); 
		
		// The Destructor 
		~BigInteger(); 
		
		// Compares Two BigInteger values irrespective of sign 
		int UnsignedCompareTo(BigInteger const&)const; 
		// Compares Two BigInteger values 
		int CompareTo(BigInteger const&)const; 
		
		// Returns Number of digits in the BigInteger 
		SizeT Digits() const; 
		// Determines if the number representation is OK or not 
		bool isValidNumber() const; 
		// True is the nubmer is zero 
		bool isZero()const; 
		
		// Straight pen-pencil implementation for addition 
		BigInteger& Add(BigInteger const&) const; 
		// Straight pen-pencil implementation for subtraction 
		BigInteger& Subtract(BigInteger const&) const; 
		// Straight pen-pencil implementation for multiplication 
		BigInteger& Multiply(BigInteger const&) const; 
		BigInteger& Multiply(DATATYPE const&) const; 
		// Straight pen-pencil implementation for division and remainder 
		BigInteger& DivideAndRemainder(BigInteger const&,BigInteger&,bool) const; 
		BigInteger& DivideAndRemainder(DATATYPE const&,DATATYPE&,bool) const; 
		
		// Overloaded Binary Operators 
		
		// Adds Two BigInteger 
		friend BigInteger& operator+(BigInteger const&, BigInteger const&); 
		// Subtructs Two BigInteger 
		friend BigInteger& operator-(BigInteger const&, BigInteger const&); 
		// Multiplies Two BigInteger 
		friend BigInteger& operator*(BigInteger const&, BigInteger const&); 
		friend BigInteger& operator*(BigInteger const&, DATATYPE const&); 
		friend BigInteger& operator*(DATATYPE const&, BigInteger const&); 
		// Divides Two BigInteger 
		friend BigInteger& DivideAndRemainder(BigInteger const&, BigInteger const&,BigInteger&,bool); 
		friend BigInteger& DivideAndRemainder(BigInteger const&, DATATYPE const&,DATATYPE&,bool); 
		friend BigInteger& operator/(BigInteger const&, BigInteger const&); 
		friend BigInteger& operator/(BigInteger const&, DATATYPE const&); 
		friend BigInteger& operator/(DATATYPE const&, BigInteger const&); 
		// Modulo Division of Two BigInteger 
		friend BigInteger& operator%(BigInteger const&, BigInteger const&); 
		friend BigInteger& operator%(BigInteger const&, DATATYPE const&); 
		friend BigInteger& operator%(DATATYPE const&, BigInteger const&); 
		
		// Assignment Operator 
		BigInteger& operator=(BigInteger const&); 
		
		// Inserter 
		friend ostream& operator<<(ostream& , BigInteger const&); 
		// Extractor 
		friend istream& operator>>(istream& , BigInteger& ); 
		
		// Overloaded Unary Operators 
		
		// Postfix Unary Increment 
		BigInteger& operator++(); 
		// Prefix Unary Increment 
		BigInteger& operator++(int); 
		
		// Postfix Unary Decrement 
		BigInteger& operator--(); 
		// Prefix Unary Decrement 
		BigInteger& operator--(int); 
		
		// Negation 
		BigInteger& operator-(); 
		
		// Bit Wise Operators 
		
		// Left Shift 
		BigInteger& operator<<(SizeT); 
		// Right Shift 
		BigInteger& operator>>(SizeT); 
		// Returns the BigInteger absolute 
		void abs(); 
		friend BigInteger& abs(BigInteger&); 
		
		// Conversion functions 
		string& toString() const; 
		int toInt(); 
		long toLong(); 
		
		// Others 
		BigInteger& Power(long )const; 
		BigInteger& SquareRoot() const; 
}; 

// Private Constructor which provides a new BigInteger Object 
// Filled with specified data 
// Useful for internal operation 
BigInteger::BigInteger(SizeT bytes,DATATYPE fill, bool toInit = true) 
{ 
	TheNumber = new DATATYPE[bytes]; 
	isNegative = false; 
	Start = 0; 
	End = bytes - 1; 
	
	if(toInit) Set(fill); 
} 

// Default Constructor 
BigInteger::BigInteger() 
{ 
	TheNumber = new DATATYPE[1]; 
	TheNumber[0] = 0; 
	Start = 0; 
	End = 0; 
	isNegative = false; 
} 

// Long Constructor 
BigInteger::BigInteger(long n) 
{ 
	if(n<0) 
	{ 
		isNegative = true; 
		n *= -1; 
	} 
	else isNegative = false; 
	
	SizeT i = (SizeT)(floor(log10((double)n)/LOG10BASE) + 1); 
	
	Start = 0; 
	End = i-1; 
	TheNumber = new DATATYPE [i]; 
	Set(0); 
	
	while(n) 
	{ 
		TheNumber[--i] = n % BASE; 
		n /= BASE; 
	} 
	TrimZeros(); 
} 

// Character array constructor 
BigInteger::BigInteger(char const* n) 
{ 
	if(n[0]=='-') { isNegative = true; n++; } 
	else if(n[0]=='+') { isNegative = false; n++; } 
	else isNegative = false; 
	
	while(*n=='0') n++; 
	
	int l = strlen(n); 
	if(l==0) 
	{ 
		*this = *new BigInteger(); 
		return; 
	} 
	Start = 0; 
	End = (SizeT)(l/LOG10BASE + l%LOG10BASE - 1); 
	TheNumber = new DATATYPE [Digits()]; 
	Set(0); 
	
	int cur = l - 1; 
	for(SizeT i = End; i>=Start;i--) 
	{ 
		if(cur<0) break; 
		DATATYPE r = 0; 
		DATATYPE TEN = 1; 
		for(l=0;l<4;l++) 
		{ 
			if(cur<0) break; 
			r = r + TEN*(n[cur]-'0'); 
			TEN *= 10; 
			cur--; 
		} 
		TheNumber[i] = r; 
	} 
	TrimZeros(); 
	if(isZero()) isNegative = false; 
} 

// Copy constructor 
BigInteger::BigInteger(BigInteger const& Temp) 
{ 
	Start = 0; 
	End = Temp.Digits() - 1; 
	TheNumber = new DATATYPE [Temp.Digits()]; 
	
	datacopy(Temp,Temp.Digits()); 
	isNegative = Temp.isNegative; 
} 

// Deallocates the array 
void BigInteger::deallocateBigInteger() 
{ 
	if(TheNumber!=0) 
	{ 
		delete [] TheNumber; 
		TheNumber = 0; 
	} 
} 

// The Destructor 
BigInteger::~BigInteger() 
{ 
	deallocateBigInteger(); 
	Start = 0; 
	End = 0; 
} 

// Sets the array with the `fill' value 
void BigInteger::Set(DATATYPE fill) 
{ 
	for(SizeT i=Start;i<=End;i++) 
		TheNumber[i] = fill; 
} 

// Copies data from `a' to `this' 
void BigInteger::datacopy(BigInteger const& a,SizeT size) 
{ 
	for(SizeT i=0;i<size;i++) 
		TheNumber[Start+i] = a.TheNumber[a.Start+i]; 
} 

// Determines the length upto valid data 
SizeT BigInteger::datalen(DATATYPE const* a) const 
{ 
	SizeT l = 0; 
	while(a[l]!=INVALIDDATA) l++; 
	return l; 
} 

// Returns number of digits in a BigInteger 
SizeT BigInteger::Digits() const 
{ return End-Start+1; } 

// true if 'this' is zero 
bool BigInteger::isZero() const 
{ return End==Start && TheNumber[Start]==0; } 

// Checks for the validity of the number 
bool BigInteger::isValidNumber() const 
{ 
	for(SizeT i=Start; i<End ; i++) 
		if(TheNumber[i]>=BASE) return false; 
		
		return true; 
} 

// Trims Leading Zeros 
void BigInteger::TrimZeros() 
{ 
	while(TheNumber[Start]==0 && Start<End) 
		Start++; 
} 

// Compares this with `with' irrespective of sign 
// Returns 
// 0 if equal 
// 1 if this>with 
// -1 if this<with 
int BigInteger::UnsignedCompareTo(BigInteger const& with)const 
{ 
	if(isZero() && with.isZero()) return 0; 
	if(!isZero() && with.isZero()) return 1; 
	if(isZero() && !with.isZero()) return -1; 
	
	long temp = Digits() - with.Digits(); 
	// Case 3: First One got more digits 
	// Case 4: First One got less digits 
	if(temp!=0) return temp<0?-1:1; 
	
	// Now I know Both have same number of digits 
	// Case 5,6,7: 
	/* 
	Compares two array of data considering the 
	case that both of them have the same number 
	of digits 
	*/ 
	
	temp = 0; 
	int cmp = 0; 
	for(SizeT i=0;i<Digits();i++) 
	{ 
		temp = TheNumber[i+Start] - with.TheNumber[i+with.Start]; 
		if(temp!=0) 
		{ 
			cmp = temp<0?-1:1; 
			break; 
		} 
	} 
	
	return cmp; 
} 

// Compares this with `with' 
// Returns 
// 0 if equal 
// 1 if this>with 
// -1 if this<with 
int BigInteger::CompareTo(BigInteger const& with)const 
{ 
	int cmp = UnsignedCompareTo(with); 
	
	// Case 1: Positive , Negative 
	if(isNegative==false && with.isNegative==true) return 1; 
	// Case 2: Negative, Positive 
	if(isNegative==true && with.isNegative==false) return -1; 
	// Now, Both are Same Sign 
	int both_neg = 1; 
	if(isNegative==true && with.isNegative==true) both_neg = -1; 
	return cmp*both_neg; 
} 

// Implentation of addition by paper-pencil method 
BigInteger& BigInteger::Add(BigInteger const& Small) const 
{ 
	BigInteger const& Big = *this; 
	BigInteger &Result= *new BigInteger(Big.Digits()+1,0); 
	
	long Carry=0,Plus; 
	long i=Big.Digits() - 1, 
		j=Small.Digits() -1; 
	
	for(; i>=0 ;i--,j--){ 
		Plus = Big.TheNumber[i+Big.Start] + Carry; 
		if(j>=0) Plus += Small.TheNumber[j+Small.Start] ; 
		
		Result.TheNumber[i+1] = Plus%BASE; 
		Carry = Plus/BASE; 
	} 
	i++; 
	
	if(Carry) Result.TheNumber[i--] = Carry; 
	
	Result.TrimZeros(); 
	
	return Result; 
} 

// Implentation of subtraction by paper-pencil method 
BigInteger& BigInteger::Subtract(BigInteger const& Small)const 
{ 
	BigInteger const& Big = *this; 
	BigInteger& Result = *new BigInteger(Big.Digits()+1,0); 
	
	long Carry=0,Minus; 
	
	long i = Big.Digits() - 1, 
		j= Small.Digits() - 1; 
	
	for( ; i>=0 ;i--,j--) 
	{ 
		Minus = Big.TheNumber[i+Big.Start] - Carry; 
		if(j>=0) Minus -= Small.TheNumber[j+Small.Start]; 
		
		if(Minus < 0) 
		{ 
			Result.TheNumber[i+1] = Minus + BASE; 
			Carry = 1; 
		} 
		else 
		{ 
			Result.TheNumber[i+1] = Minus; 
			Carry = 0; 
		} 
	} 
	Result.TrimZeros(); 
	return Result; 
} 

// Addition operator 
BigInteger& operator+(BigInteger const& N1, BigInteger const& N2) 
{ 
	if(N1.isNegative && !N2.isNegative) 
	{ 
		// First is negaive and second is not 
		BigInteger& Res = *new BigInteger(N1); 
		Res.isNegative = false; 
		Res = N2-Res; 
		return Res; 
	} 
	if(!N1.isNegative && N2.isNegative) 
	{ 
		// Second is negaive and first is not 
		BigInteger& Res = *new BigInteger(N2); 
		Res.isNegative = false; 
		Res = N1-Res; 
		return Res; 
	} 
	
	BigInteger& ret = *new BigInteger(); 
	
	if(N1.UnsignedCompareTo(N2)<0) 
		ret = N2.Add(N1); 
	else 
		ret = N1.Add(N2); 
	if(N1.isNegative==true && N2.isNegative==true) 
		ret.isNegative = true; 
	return ret; 
} 

// Subtruction operator 
BigInteger& operator-(BigInteger const& N1, BigInteger const& N2) 
{ 
	if(N1.isNegative && !N2.isNegative) 
	{ 
		BigInteger& res = *new BigInteger(N1); 
		res.isNegative = false; 
		res = res+N2; 
		res.isNegative = true; 
		return res; 
	} 
	if(!N1.isNegative && N2.isNegative) 
	{ 
		BigInteger& res = *new BigInteger(N2); 
		res.isNegative = false; 
		res = res+N1; 
		return res; 
	} 
	
	
	BigInteger& ret = *new BigInteger(); 
	int cmp = N1.UnsignedCompareTo(N2); 
	if(cmp==0) 
	{ 
		ret = *new BigInteger(); 
	} 
	if(cmp<0) 
	{ 
		ret = N2.Subtract(N1); 
		ret.isNegative = true; 
	} 
	else 
	{ 
		ret = N1.Subtract(N2); 
		ret.isNegative = false; 
	} 
	return ret; 
} 

// Implentation of multiplication by paper-pencil method 
BigInteger& BigInteger::Multiply(BigInteger const& Small) const 
{ 
	BigInteger const& Big = *this; 
	BigInteger& Result = *new BigInteger(Big.Digits()+Small.Digits(),0); 
	
	long Carry,Multiply; 
	
	SizeT i; 
	SizeT j; 
	
	for(i = 0 ; i< Small.Digits() ; i++) 
	{ 
		Carry = 0; 
		for(j = 0 ; j< Big.Digits() ; j++) 
		{ 
			Multiply = ( (long)Small.TheNumber[Small.End-i] * (long)Big.TheNumber[Big.End-j] ) 
				+ Carry + Result.TheNumber[Result.End-i-j]; 
			Result.TheNumber[Result.End-i-j] = Multiply%BASE; 
			Carry = Multiply/BASE ; 
		} 
		Result.TheNumber[Result.End-i-j] = Carry; 
	} 
	
	Result.TrimZeros(); 
	
	return Result; 
} 

// Implentation of multiplication by paper-pencil method 
// See: D. E. Knuth 4.3.1 
BigInteger& BigInteger::Multiply(DATATYPE const& with) const 
{ 
	BigInteger& Result = *new BigInteger(Digits()+1,0); 
	
	long Carry,Multiply; 
	
	SizeT i; 
	
	Carry = 0; 
	for(i = 0 ; i< Digits() ; i++) 
	{ 
		Multiply = Carry + (long)TheNumber[End-i] * (long)with; 
		Carry = Multiply / BASE; 
		Result.TheNumber[Result.End-i] = Multiply % BASE; 
	} 
	Result.TheNumber[Result.End-i] = Carry; 
	Result.TrimZeros(); 
	
	return Result; 
} 

// Multiplication operator 
BigInteger& operator*(BigInteger const& N1, BigInteger const& N2) 
{ 
	if(N1.isZero() || N2.isZero()) return *new BigInteger(); 
	BigInteger& ret = *new BigInteger(); 
	if(N1.UnsignedCompareTo(N2)<0) 
		ret = N2.Multiply(N1); 
	else 
		ret = N1.Multiply(N2); 
	if(N1.isNegative!=N2.isNegative) 
		ret. isNegative = true; 
	return ret; 
} 

// Multiplication operator 
BigInteger& operator*(BigInteger const& N1, DATATYPE const& N2) 
{ 
	if(N1.isZero() || N2==0) return *new BigInteger(); 
	BigInteger& ret = N1.Multiply(N2); 
	// if(N1.isNegative!=(N2<0)) ret. isNegative = true; 
	return ret; 
} 

// Multiplication operator 
BigInteger& operator*(DATATYPE const& N1, BigInteger const& N2) 
{ 
	if(N2.isZero() || N1==0) return *new BigInteger(); 
	BigInteger& ret = N2.Multiply(N1); 
	// if(N2.isNegative!=(N1<0)) ret. isNegative = true; 
	return ret; 
} 

// Implentation of division by paper-pencil method 
// Here `this' is divided by 'V' 
BigInteger& BigInteger::DivideAndRemainder(DATATYPE const& V,DATATYPE& _R,bool skipRemainder=false) const 
{ 
	BigInteger& W = *new BigInteger(Digits(),0,false); 
	DATATYPE R = 0; 
	SizeT j; 
	for(j=0;j<=End;j++) 
	{ 
		W.TheNumber[j] = (R*BASE+TheNumber[Start+j])/V; 
		R = (R*BASE+TheNumber[Start+j])%V; 
	} 
	
	W.TrimZeros(); 
	if(skipRemainder==false) 
		_R = R; 
	
	return W; 
} 

// Implentation of division by paper-pencil method 
// Does not perform the validity and sign check 
// It is assumed that this > `_V' 
// See: D.E.Knuth 4.3.1 
BigInteger& BigInteger::DivideAndRemainder(BigInteger const& _V,BigInteger& R,bool skipRemainder=false) const 
{ 
	SizeT m = this->Digits()-_V.Digits(); 
	SizeT n = _V.Digits(); 
	BigInteger& Q = *new BigInteger(m+1,0,false); 
	
	DATATYPE d, qhat, rhat; 
	long temp,x,y; 
	SizeT i; 
	int j; 
	
	d = (BASE-1)/_V.TheNumber[_V.Start]; 
	
	BigInteger& U = this->Multiply(d); 
	BigInteger& V = _V.Multiply(d); 
	
	for(j = m; j>=0; j--) 
	{ 
		temp = (long)U.TheNumber[U.End-j-n]*(long)BASE + (long)U.TheNumber[U.End-j-n+1]; 
		x = temp / (long)V.TheNumber[V.Start]; 
		y = temp % (long)V.TheNumber[V.Start]; 
		if(x>(long)BASE) x /= BASE; 
		if(y>(long)BASE) y %= BASE; 
		qhat = (DATATYPE) x; 
		rhat = (DATATYPE) y; 
		
		bool badRhat = false; 
		do 
		{ 
			x = (long)qhat * (long)V.TheNumber[V.Start+1]; 
			y = (long)BASE*(long)rhat + (long)U.TheNumber[U.End-j-n+1]; 
			
			if(qhat==BASE || x > y) 
			{ 
				qhat --; 
				rhat += V.TheNumber[V.Start]; 
				if(rhat<BASE) badRhat = true; 
				else badRhat = false; 
			} 
			else break; 
		}while(badRhat); 
		
		// `x' Will act as Carry in the next loop 
		x = 0; 
		temp = 0; 
		for(i=0;i<=n;i++) 
		{ 
			if(V.End>=i) temp = (long)qhat*(long)V.TheNumber[V.End-i] + temp; 
			y = (long)U.TheNumber[U.End-j-i] - temp%BASE - x; 
			temp /= BASE; 
			if(y < 0) 
			{ 
				U.TheNumber[U.End-j-i] = (DATATYPE)(y+BASE); 
				x = 1; 
			} 
			else 
			{ 
				U.TheNumber[U.End-j-i] = (DATATYPE)y; 
				x = 0; 
			} 
		} 
		// if(x) U.TheNumber[U.Start+j+i] --; 
		
		Q.TheNumber[Q.End-j] = qhat; 
		
		if(x) 
		{ 
			Q.TheNumber[Q.End-j] --; 
			// `x' Will act as Carry in the next loop 
			x = 0; 
			for(i=0;i<=n;i++) 
			{ 
				y = (long)U.TheNumber[U.End-j-i] + x; 
				if(V.End>=i) y += (long)V.TheNumber[V.End-i]; 
				U.TheNumber[U.End-j-i] = (DATATYPE)(y % BASE); 
				x = y / BASE; 
			} 
			U.TheNumber[U.End-j-i] = (DATATYPE)x; 
		} 
	} 
	
	U.TrimZeros(); 
	DATATYPE _t; 
	if(skipRemainder==false) 
		R = U.DivideAndRemainder(d,_t,true); 
	Q.TrimZeros(); 
	
	return Q; 
} 

// Front end for Divide and Remainder 
// Performs the validity and sign check 
BigInteger& DivideAndRemainder(BigInteger const& U, BigInteger const& V,BigInteger& R,bool skipRemainder=false) 
{ 
	if(V.isZero()) 
		throw logic_error (DumpString ("DivideAndRemainder (BigInteger/BigInteger)",BigMathDIVIDEBYZERO)); 
	
	if(U.isZero()) 
	{ 
		R = *new BigInteger(); 
		return *new BigInteger(); 
	} 
	
	int cmp = U.UnsignedCompareTo(V); 
	if(cmp==0) 
	{ 
		R = *new BigInteger(); 
		BigInteger& W = *new BigInteger(1l); 
		if(U.isNegative!=V.isNegative) W.isNegative = true; 
		return W; 
	} 
	else if(cmp<0) 
	{ 
		R = *new BigInteger(U); 
		if(U.isNegative!=V.isNegative) R.isNegative = true; 
		return *new BigInteger(); 
	} 
	BigInteger& ret = U.DivideAndRemainder(V,R,skipRemainder); 
	if(U.isNegative!=V.isNegative) ret.isNegative = true; 
	return ret; 
} 

// Front end for Divide and Remainder 
// Performs the validity and sign check 
BigInteger& DivideAndRemainder(BigInteger const& U, DATATYPE const& V,DATATYPE& R,bool skipRemainder=false) 
{ 
	if(V==0) 
		throw logic_error ( DumpString ("DivideAndRemainder (BigInteger/DATATYPE)",BigMathDIVIDEBYZERO) ); 
	
	if(U.isZero()) 
	{ 
		R = 0; 
		return *new BigInteger(); 
	} 
	
	int cmp = 1; 
	if(U.Digits()==1) 
	{ 
		if(U.TheNumber[U.Start]<V) cmp = -1; 
		else if(U.TheNumber[U.Start]>V) cmp = 1; 
		else cmp = 0; 
	} 
	if(cmp==0) 
	{ 
		R = 0; 
		return *new BigInteger(1l); 
	} 
	else if(cmp<0) 
	{ 
		R = U.TheNumber[U.Start]; 
		return *new BigInteger(); 
	} 
	BigInteger& ret = U.DivideAndRemainder(V,R,skipRemainder); 
	// if(U.isNegative!=(V<0)) ret.isNegative = true; 
	return ret; 
} 

// Division operator 
BigInteger& operator/(BigInteger const& N1, BigInteger const& N2) 
{ 
	BigInteger& R = *new BigInteger(); 
	return DivideAndRemainder(N1,N2,R,true); 
} 

// Division operator 
BigInteger& operator/(BigInteger const& U, DATATYPE const& V) 
{ 
	DATATYPE R; 
	return DivideAndRemainder(U,V,R,true); 
} 

// Division operator 
BigInteger& operator/(DATATYPE const& U, BigInteger const& V) 
{ 
	if(V.Digits()==1 && U>V.TheNumber[V.Start]) 
	{ 
		return *new BigInteger(U/V.TheNumber[V.Start]); 
	} 
	return *new BigInteger(); 
} 

// Modulus operator 
BigInteger& operator%(BigInteger const& N1,BigInteger const& N2) 
{ 
	BigInteger& R = *new BigInteger(); 
	DivideAndRemainder(N1,N2,R); 
	return R; 
} 

// Modulus operator 
BigInteger& operator%(BigInteger const& U, DATATYPE const& V) 
{ 
	DATATYPE R; 
	DivideAndRemainder(U,V,R); 
	return *new BigInteger(R); 
} 

// Modulus operator 
BigInteger& operator%(DATATYPE const& U, BigInteger const& V) 
{ 
	if(V.Digits()==1 && U>V.TheNumber[V.Start]) 
	{ 
		return *new BigInteger(U%V.TheNumber[V.Start]); 
	} 
	return *new BigInteger(); 
} 

// Assignment Operator 
BigInteger& BigInteger::operator=(BigInteger const&arg) 
{ 
	Start = 0; 
	End = arg.Digits() - 1; 
	delete [] TheNumber; 
	TheNumber = new DATATYPE [arg.Digits()]; 
	
	datacopy(arg,arg.Digits()); 
	isNegative = arg.isNegative; 
	return *this; 
} 

// Inserter 
ostream& operator<<(ostream& stream, BigInteger const& out) 
{ 
	if(out.isNegative==true && out.isZero()==false) stream << '-'; 
	stream << out.TheNumber[out.Start]; 
	for(SizeT i=out.Start+1;i<=out.End;i++) 
	{ 
		stream.width(4); 
		stream.fill('0'); 
		stream << out.TheNumber[i]; 
	} 
	
	return stream; 
} 

// Extracter 
istream& operator>>(istream& stream, BigInteger& in) 
{ 
	SizeT SIZE = 500; 
	char *data = new char[SIZE]; 
	// if(data==0) Dump("Extractor operator",BigMathMEM); 
	SizeT i = 0; 
	int input; 
	bool isNegative = false; 
	stream >> ws; 
	input = stream.get(); 
	if(input=='-') isNegative = true; 
	else if(input=='+') isNegative = false; 
	else stream.putback(input); 
	
	while(true) 
	{ 
		input = stream.get(); 
		if(isdigit(input)) 
			data[i++] = input; 
		else 
		{ 
			stream.putback(input); 
			break; 
		} 
		if(i>=SIZE) 
		{ 
			SIZE += SIZE; 
			char *p = new char [SIZE]; 
			// if(p==0) Dump("Extractor operator",BigMathMEM); 
			strcpy(p,data); 
			delete [] data; 
			data = p; 
		} 
	} 
	data[i] = 0; 
	in = *new BigInteger(data); 
	if(in.isZero()==false) 
		in.isNegative = isNegative; 
	return stream; 
} 

// Inserts the version information into the output stream 
ostream& BigIntegerVersion(ostream& out) 
{ 
	out << BigIntPROGRAMNAME << " (Version "<< BigIntMajorVersion 
		<< "." << BigIntMinorVersion << "." << BigIntRevision << ")"; 
	return out; 
} 

// Inserts the author information into the output stream 
ostream& BigIntegerAuthor(ostream& out) 
{ 
	out << "Author: S. M. Mahbub Murshed" << 
		endl << "mailto: suman@bttb.net.bd"; 
	return out; 
} 

// Inserts the about information into the output stream 
ostream& BigIntegerAbout(ostream& out) 
{ 
	out << BigIntegerVersion << endl << BigIntegerAuthor << endl; 
	return out; 
} 

// Returns a string containing version information 
string& BigIntegerVersionString() 
{ 
	char out[100]; 
	ostrstream str(out,sizeof(out)); 
	str << BigIntegerVersion; 
	return *new string(out); 
} 

// Converts `this' to a string representation 
string& BigInteger::toString()const 
{ 
	const int DIGITS = Digits()*4; 
	char *R = new char[DIGITS+2]; 
	ostrstream ostr(R,DIGITS); 
	ostr << *this; 
	return *new string(R); 
} 

// Converts `this' to equivalent int value 
int BigInteger::toInt() 
{ 
	return (int)toLong(); 
} 

// Converts `this' to equivalent 32 bit long value 
long BigInteger::toLong() 
{ 
	long r = TheNumber[End]; 
	if(Digits()>1) r += BASE * TheNumber[End-1] ; 
	if(Digits()>2) r += BASE*BASE*(TheNumber[End-2]%100); 
	return r; 
} 

// Postfix Increment , that is *this++ 
BigInteger& BigInteger::operator++() 
{ 
	BigInteger& ONE = *new BigInteger(1l); 
	*this = *this+ONE; 
	return *this; 
} 

// Prefix Increment , that is ++*this 
BigInteger& BigInteger::operator++(int notused) 
{ 
	BigInteger one(1l); 
	BigInteger& Ret = *new BigInteger(*this); 
	*this = *this+one; 
	return Ret; 
} 

// Postfix Decrement , that is *this-- 
BigInteger& BigInteger::operator--() 
{ 
	BigInteger one(1l); 
	*this = *this-one; 
	return *this; 
} 

// Pretfix Increment , that is --*this 
BigInteger& BigInteger::operator--(int notused) 
{ 
	BigInteger one(1l); 
	BigInteger& Ret = *new BigInteger(*this); 
	*this = *this-one; 
	return Ret; 
} 

// Negation, returns -*this 
BigInteger& BigInteger::operator-() 
{ 
	this->isNegative = this->isNegative==true?false:true; 
	return *this; 
} 

// Left Shift 
// To be checked 
BigInteger& BigInteger::operator<<(SizeT b) 
{ 
	SizeT i = (SizeT)(b / LOG10BASE); 
	b %= LOG10BASE; 
	while(b--) TheNumber[Digits()-1] *= 10; 
	
	if(i>0) 
	{ 
		DATATYPE *temp = new DATATYPE[Digits()+i]; 
		for(b=0;b<Digits();b++) 
			temp[b] = TheNumber[b]; 
		for(b=0;b<i; b++) 
			temp[Digits()+b] = 0; 
		delete [] TheNumber; 
		TheNumber = temp; 
		End += i-1; 
	} 
	return *this; 
} 

// Right Shift 
BigInteger& BigInteger::operator>>(SizeT b) 
{ 
	SizeT i = (SizeT)(b / LOG10BASE); 
	b %= LOG10BASE; 
	End -= i; 
	while(b--) 
	{ 
		DATATYPE f = 0,l = 0; 
		for(i=Start;i<=End;i++) 
		{ 
			l = TheNumber[i]%10; 
			TheNumber[i] = f*BASE + TheNumber[i]/10; 
			f = l; 
		} 
		if(TheNumber[Start]==0) 
			Start--; 
	} 
	return *this; 
} 

// Makes `this' BigInteger value to absolute 
void BigInteger::abs() 
{ isNegative = false; } 

// Returns new BigInteger value which is absolute 
// copy of `arg' 
BigInteger& abs(BigInteger& arg) 
{ 
	BigInteger& ret = *new BigInteger(arg); 
	ret.isNegative = false; 
	return ret; 
} 

// Power BigInteger to the power Long 
BigInteger& BigInteger::Power(long y) const 
{ 
	long P; 
	BigInteger& pow = *new BigInteger(1l); 
	BigInteger& z = *new BigInteger(); 
	BigInteger& ZERO = *new BigInteger(); 
	BigInteger& ONE = *new BigInteger(1l); 
	P = y; 
	
	if(y==0) return pow; 
	if(isZero()) return ZERO; 
	if(UnsignedCompareTo(ONE)==0) return ONE; 
	
	z = *this; 
	while(P>0) 
	{ 
		while(P%2==0) 
		{ 
			P /= 2; 
			z = z*z; 
		} 
		P--; 
		pow = pow*z; 
	} 
	return pow; 
} 

void Dump(char const* s,enum BigMathERROR e) 
{ 
	cerr << BigIntegerVersion << endl; 
	cerr << "Exception: " << BigIntErrDes[e-1] << endl; 
	cerr << "In function: " << s << endl; 
	cerr << "Error Code: " << e << endl; 
	exit(e); 
} 

string& DumpString (char const* s,enum BigMathERROR e) 
{ 
	char *R = new char[256]; 
	ostrstream ostr(R,255); 
	ostr << BigIntegerVersion << endl; 
	ostr << "Exception: " << BigIntErrDes[e-1] << endl; 
	ostr << "In function: " << s << endl; 
	ostr << "Error Code: " << e << endl; 
	return *new string(R); 
} 

BigInteger& BigInteger::SquareRoot() const 
{ 
	BigInteger const& n = *this; 
	BigInteger& _2 = *new BigInteger(2l); 
	BigInteger& zero = *new BigInteger(); 
	if(n.isZero()) 
		return zero; 
	
	if(n.isNegative) 
		throw domain_error ( DumpString ("Square Root",BigMathDomain) ); 
	
	long Dig; 
	if(n.Digits()%2==0) 
		Dig = n.Digits()/2 - 1; 
	else 
		Dig = n.Digits()/2 ; 
	
	BigInteger& sq = *new BigInteger(1l); 
	if(Dig==-1) 
		return sq; 
	
	BigInteger sqr,toIncrease,temp; 
	sq = sq << Dig; 
	toIncrease = sq; 
	
	while(true) 
	{ 
		sqr = sq*sq; 
		if(sqr.CompareTo(n) == 0) break; 
		if(toIncrease.CompareTo(zero)==0) break; 
		if(sqr.CompareTo(n) > 0) 
		{ 
			toIncrease = toIncrease/_2; 
			sq = temp; 
		} 
		
		temp = sq; 
		sq = sq + toIncrease; 
	} 
	return sq; 
} 

bool operator==(BigInteger const& a, BigInteger const& b) 
{ return a.CompareTo(b)==0; } 

bool operator!=(BigInteger const& a, BigInteger const& b) 
{ return a.CompareTo(b)!=0; } 

bool operator>=(BigInteger const& a, BigInteger const& b) 
{ return a.CompareTo(b)>=0; } 

bool operator<=(BigInteger const& a, BigInteger const& b) 
{ return a.CompareTo(b)<=0; } 

bool operator>(BigInteger const& a, BigInteger const& b) 
{ return a.CompareTo(b)>0; } 

bool operator<(BigInteger const& a, BigInteger const& b) 
{ return a.CompareTo(b)<0; } 
} 

---

경시대회준비반