bigtypes.h

基于SD卡的软实现CSP程序

			}
		}
		
		else
			if ( ugreater( b, r ) )
			{
				ushiftRight1( b );
				
				--shifts;
			}
			
		u32 qshifts = 0;
		
		while ( shifts-- )
		{
			++qshifts;
			
			if ( !ugreater( b, r ) )
			{
				subtract( r, b );
				
				shiftLeft( q, qshifts );
				qshifts = 0;
				
				q[ 0 ] |= 1;
			}
			
			ushiftRight1( b );
		}
		
		shiftLeft( q, qshifts );
	}
	
	// r = a Mod b, unsigned
	BIGONETYPE void umodulo( T &a, T &b0, T &r )
	{
		T b;
		u32 shifts = 1;
		
		set ( b, b0 )
		
		;
		set ( r, a )
		
		;
		
		if ( !BIGHIGHBIT( b ) && ugreater( r, b ) )
		{
			s32 ii, jj;
			
			// shift by words if possible
			
			for ( ii = BIGWORDCOUNT( T ) - 1; ii >= 0; --ii )
				if ( r[ ii ] )
					break;
					
			for ( jj = ii; jj >= 0; --jj )
				if ( b[ jj ] )
					break;
					
			if ( ii != jj )
			{
				shifts = ( ii - jj ) * WORDBITS;
				shiftLeft( b, shifts );
				++shifts;
			}
			
			while ( !BIGHIGHBIT( b ) && ugreater( r, b ) )
			{
				shiftLeft1( b );
				
				++shifts;
			}
			
			while ( ugreater( b, r ) )
			{
				ushiftRight1( b );
				
				--shifts;
			}
		}
		
		else
			if ( ugreater( b, r ) )
			{
				ushiftRight1( b );
				
				--shifts;
			}
			
		while ( shifts-- )
		{
			if ( !ugreater( b, r ) )
				subtract( r, b );
				
			ushiftRight1( b );
		}
	}
	
	// {q, r} = a / b (&q != &r), signed
	BIGONETYPE void sdivide( T &a, T &b0, T &q, T &r )
	{
		T b;
		
		set ( b, b0 )
		
		;
		set ( r, a )
		
		;
		zero( q );
		
		word sign_a = BIGHIGHBIT( a );
		
		if ( sign_a )
			negate( r );
			
		word sign_b = BIGHIGHBIT( b );
		
		if ( sign_b )
			negate( b );
			
		u32 shifts = 1;
		
		if ( !BIGHIGHBIT( b ) && ugreater( r, b ) )
		{
			s32 ii, jj;
			
			// shift by words if possible
			
			for ( ii = BIGWORDCOUNT( T ) - 1; ii >= 0; --ii )
				if ( r[ ii ] )
					break;
					
			for ( jj = ii; jj >= 0; --jj )
				if ( b[ jj ] )
					break;
					
			if ( ii != jj )
			{
				shifts = ( ii - jj ) * WORDBITS;
				shiftLeft( b, shifts );
				++shifts;
			}
			
			while ( !BIGHIGHBIT( b ) && ugreater( r, b ) )
			{
				shiftLeft1( b );
				
				++shifts;
			}
			
			while ( ugreater( b, r ) )
			{
				ushiftRight1( b );
				
				--shifts;
			}
		}
		
		else
			if ( ugreater( b, r ) )
			{
				ushiftRight1( b );
				
				--shifts;
			}
			
		u32 qshifts = 0;
		
		while ( shifts-- )
		{
			++qshifts;
			
			if ( !ugreater( b, r ) )
			{
				subtract( r, b );
				
				shiftLeft( q, qshifts );
				qshifts = 0;
				
				q[ 0 ] |= 1;
			}
			
			ushiftRight1( b );
		}
		
		shiftLeft( q, qshifts );
		
		if ( sign_a ^ sign_b )
			negate( q );
			
		if ( sign_a )
			negate( r );
	}
	
	// r = a Mod b, signed
	BIGONETYPE void smodulo( T &a, T &b0, T &r )
	{
		T b;
		u32 shifts = 1;
		
		set ( b, b0 )
		
		;
		set ( r, a )
		
		;
		
		word sign_a = BIGHIGHBIT( a );
		
		if ( sign_a )
			negate( r );
			
		word sign_b = BIGHIGHBIT( b );
		
		if ( sign_b )
			negate( b );
			
		if ( !BIGHIGHBIT( b ) && ugreater( r, b ) )
		{
			s32 ii, jj;
			
			// shift by words if possible
			
			for ( ii = BIGWORDCOUNT( T ) - 1; ii >= 0; --ii )
				if ( r[ ii ] )
					break;
					
			for ( jj = ii; jj >= 0; --jj )
				if ( b[ jj ] )
					break;
					
			if ( ii != jj )
			{
				shifts = ( ii - jj ) * WORDBITS;
				shiftLeft( b, shifts );
				++shifts;
			}
			
			while ( !BIGHIGHBIT( b ) && ugreater( r, b ) )
			{
				shiftLeft1( b );
				
				++shifts;
			}
			
			while ( ugreater( b, r ) )
			{
				ushiftRight1( b );
				
				--shifts;
			}
		}
		
		else
			if ( ugreater( b, r ) )
			{
				ushiftRight1( b );
				
				--shifts;
			}
			
		while ( shifts-- )
		{
			if ( !ugreater( b, r ) )
				subtract( r, b );
				
			ushiftRight1( b );
		}
		
		if ( sign_a )
			negate( r );
	}
	
	
	//////// converting to/from strings ////////
	
#ifdef BIG_USES_STRINGS
	
	// n -> string
	BIGONETYPE std::string toString( T &n0, bool sign = true, u16 radix = 10 )
	{
		T n, base, r;
		std::string s;
		
		set ( n, n0 )
		
		;
		usetw( base, radix );
		
		word sign_n = 0;
		
		if ( sign && ( sign_n = BIGHIGHBIT( n ) ) )
			negate( n );
			
		do // always allow first iteration for zero
		{
			// {q, r} = n / base
			udivide( n, base, n, r );
			
			char ch = ( char ) r[ 0 ];
			
			if ( ch >= 10 )
				ch += 'a' - 10;
			else
				ch += '0';
				
			// insert character
			s = ch + s;
		}
		
		while ( !isZero( n ) );
		
		if ( sign_n )
			s = '-' + s;
			
		return s;
	}
	
	// s -> n, signed
	BIGONETYPE void fromString( std::string s, T &n, bool sign = true, u16 radix = 10 )
	{
		T acc, base, temp;
		
		usetw( acc, 1 );
		usetw( base, radix );
		zero( n );
		
		u32 len = ( u32 ) s.length();
		const char *citer = s.c_str() + len;
		
		while ( len-- )
		{
			char ch = *( --citer );
			
			if ( IS_ALPHA( ch ) )   // assumes alpha characters only up to radix
				ch = TO_LOWER( ch ) - 'a' + 10;
			else
				if ( sign && ch == '-' )   // '-' should be first character
				{
					negate( n );
					break;
				}
				else // assumes it's alphanumeric/-
					ch -= '0';
					
			usetw( temp, ch );
			
			umultiply( temp, acc );
			
			add ( n, temp )
			
			;
			
			umultiply( acc, base );
		}
	}
	
#endif // BIG_USES_STRINGS
	
	
	//////// class wrapper ////////
	
	BIGONETYPE INLINE Int<T>::Int()
	{
		big::zero( raw );
	}
	
	BIGONETYPE INLINE Int<T>::Int( word n )
	{
		ssetw( raw, n );
	}
	
#ifdef BIG_USES_STRINGS
	
	BIGONETYPE INLINE Int<T>::Int( std::string &s )
	{
		fromString( s, raw );
	}
	
#endif
	
	BIGONETYPE INLINE Int<T>::Int( T &n )
	{
		set ( raw, n )
		
		;
	}
	
	BIGONETYPE INLINE Int<T>::operator T &()
	{
		return raw;
	}
	
	
	BIGONETYPE BIGINTFAST Int<T>::zero()
	{
		big::zero( raw );
		return *this;
	}
	
	BIGONETYPE BIGINTFAST Int<T>::operator=( word n )
	{
		ssetw( raw, n );
		return *this;
	}
	
	BIGONETYPE BIGINTFAST Int<T>::operator=( T &n )
	{
		set ( raw, n )
		
		;
		return *this;
	}
	
	
	BIGONETYPE BIGINTFAST Int<T>::operator<<=( u32 s )
	{
		shiftLeft( raw, s );
		return *this;
	}
	
	BIGONETYPE BIGINTSLOW Int<T>::operator<<( u32 s )
	{
		Int<T> temp( raw );
		return temp <<= s;
	}
	
	BIGONETYPE BIGINTFAST Int<T>::operator>>=( u32 s )
	{
		shiftRight( raw, s );
		return *this;
	}
	
	BIGONETYPE BIGINTSLOW Int<T>::operator>>( u32 s )
	{
		Int<T> temp( raw );
		return temp >>= s;
	}
	
	
	BIGONETYPE BIGINTFAST Int<T>::operator+=( T &n )
	{
		add ( raw, n )
		
		;
		return *this;
	}
	
	BIGONETYPE BIGINTSLOW Int<T>::operator+( T &n )
	{
		Int<T> temp( raw );
		return temp += n;
	}
	
	BIGONETYPE BIGINTFAST Int<T>::operator-=( T &n )
	{
		subtract( raw, n );
		return *this;
	}
	
	BIGONETYPE BIGINTSLOW Int<T>::operator-( T &n )
	{
		Int<T> temp( raw );
		return temp -= n;
	}
	
	BIGONETYPE BIGINTFAST Int<T>::operator++()   // prefix
	{
		increment( raw );
		return *this;
	}
	
	BIGONETYPE BIGINTSLOW Int<T>::operator++( int )   // postfix
	{
		Int<T> temp( raw );
		increment( raw );
		return temp;
	}
	
	BIGONETYPE BIGINTFAST Int<T>::operator--()   // prefix
	{
		decrement( raw );
		return *this;
	}
	
	BIGONETYPE BIGINTSLOW Int<T>::operator--( int )   // postfix
	{
		Int<T> temp( raw );
		decrement( raw );
		return temp;
	}
	
	
	BIGONETYPE BIGINTSLOW Int<T>::operator-( int )   // negation
	{
		Int<T> temp( raw );
		negate( temp );
		return temp;
	}
	
	
	BIGONETYPE BIGINTSLOW Int<T>::operator*( T &n )
	{
		Int<T> temp( raw );
		return temp *= n;
	}
	
	BIGONETYPE BIGINTFAST Int<T>::square()
	{
		square( raw );
		return *this;
	}
	
	
	BIGONETYPE BIGINTFAST Int<T>::operator/=( T &n )
	{
		T discard;
		divide( raw, n, raw, discard );
		return *this;
	}
	
	BIGONETYPE BIGINTSLOW Int<T>::operator/( T &n )
	{
		Int<T> temp( raw );
		return temp /= n;
	}
	
	BIGONETYPE BIGINTFAST Int<T>::operator%=( T &n )
	{
		modulus( raw, n, raw );
		return *this;
	}
	
	BIGONETYPE BIGINTSLOW Int<T>::operator%( T &n )
	{
		Int<T> temp( raw );
		return temp %= n;
	}
	
	
	BIGONETYPE INLINE /* fast */ bool Int<T>::operator>( T &n )
	{
		return sgreater( raw, n );
	}
	
	BIGONETYPE INLINE /* fast */ bool Int<T>::operator>=( T &n )
	{
		return sgreaterOrEqual( raw, n );
	}
	
	BIGONETYPE INLINE /* fast */ bool Int<T>::operator<( T &n )
	{
		return !sgreaterOrEqual( raw, n );
	}
	
	BIGONETYPE INLINE /* fast */ bool Int<T>::operator<=( T &n )
	{
		return !sgreater( raw, n );
	}
	
	BIGONETYPE INLINE /* fast */ bool Int<T>::operator==( T &n )
	{
		return equal( raw, n );
	}
	
	BIGONETYPE INLINE /* fast */ bool Int<T>::operator!=( T &n )
	{
		return !equal( raw, n );
	}
	
	BIGONETYPE INLINE /* fast */ bool Int<T>::operator!()
	{
		return isZero( raw );
	}
	
#ifdef BIG_USES_STRINGS
	
	BIGONETYPE INLINE /* fast */ std::string Int<T>::str()
	{
		return toString( raw );
	}
	
	BIGONETYPE BIGINTFAST Int<T>::operator=( std::string &s )
	{
		fromString( s, raw );
		return *this;
	}
	
	BIGONETYPE BIGINTFAST Int<T>::operator=( const char *s )
	{
		fromString( std::string( s ), raw );
		return *this;
	}
	
#endif // BIG_USES_STRINGS
}

#endif // #if !defined(_COMPATIBILITY_1)

#endif // BIGTYPES_H

#ifdef _MSC_VER
#pragma warning( pop )
#endif