#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;}