Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
代码:欢迎来我博客http://hodgezhang.sinaapp.com/?p=184#include <string> #include <algorithm> #include <iostream> #include <sstream> #include <vector> using namespace std; class BigInteger { public: BigInteger(int v=0); BigInteger(string str); BigInteger(const BigInteger &); BigInteger & operator= (const BigInteger &); BigInteger & operator+= (const BigInteger &); BigInteger & operator-= (const BigInteger &); BigInteger & operator*= (const BigInteger &); BigInteger & operator/= (const BigInteger &); BigInteger & operator%= (const BigInteger &); public: string str_repr() const; public: friend BigInteger operator+ (const BigInteger &, const BigInteger &); friend BigInteger operator- (const BigInteger &, const BigInteger &); friend BigInteger operator* (const BigInteger &, const BigInteger &); friend BigInteger operator/ (const BigInteger &, const BigInteger &); friend BigInteger operator% (const BigInteger &, const BigInteger &); friend bool operator> (const BigInteger &, const BigInteger &); friend bool operator< (const BigInteger &, const BigInteger &); friend bool operator>= (const BigInteger &, const BigInteger &); friend bool operator<= (const BigInteger &, const BigInteger &); friend bool operator== (const BigInteger &, const BigInteger &); public: friend istream & operator>> (istream & in, BigInteger & num); friend ostream & operator<< (ostream & out, const BigInteger & num); private: friend BigInteger unsign_plus (const BigInteger &, const BigInteger &); friend BigInteger unsign_minus (const BigInteger &, const BigInteger &); friend BigInteger unsign_multiply (const BigInteger &, const BigInteger &); friend BigInteger unsign_divide (const BigInteger &, const BigInteger &); friend BigInteger unsign_mod (const BigInteger &, const BigInteger &); friend bool unsign_greater (const BigInteger &, const BigInteger &); friend bool unsign_less (const BigInteger &, const BigInteger &); friend bool unsign_greater_equal (const BigInteger &, const BigInteger &); friend bool unsign_less_equal (const BigInteger &, const BigInteger &); friend bool unsign_equal (const BigInteger &, const BigInteger &); private: void string2vector(string & str); //store a string representation of an unsigned big integer in the vector string vector2string() const; //convert an unsigned big integer stored in the vector to a string representation int string2int(string & str) const; string int2string(int val) const; private: bool _positive; vector<int> _vec; //Each position in _vec is used to store an integer less than MAX_UNIT. public: static unsigned int MAX_UNIT; static unsigned int UNIT_LEN; }; BigInteger::BigInteger(int v) { if(v == 0) { _positive = true; _vec.push_back(0); return; } if(v < 0) { _positive = false; v = -1 * v; } else _positive = true; while(v > 0) { _vec.push_back(v % MAX_UNIT); v /= MAX_UNIT; } } BigInteger::BigInteger(string str) { if(str.empty()) BigInteger(0); else { _positive = true; if(str[0] == '+' || str[0] == '-') { if(str[0] == '-') _positive = false; str = str.substr(1); } string2vector(str); } } BigInteger::BigInteger(const BigInteger & bigInt) { if(&bigInt != this) { _positive = bigInt._positive; _vec = bigInt._vec; } } BigInteger & BigInteger::operator=(const BigInteger & bigInt) { if(&bigInt != this) { _positive = bigInt._positive; _vec = bigInt._vec; } return *this; } BigInteger & BigInteger::operator+=(const BigInteger & second) { BigInteger result = (*this) + second; *this = result; return *this; } BigInteger & BigInteger::operator-= (const BigInteger & second) { BigInteger result = (*this) - second; *this = result; return *this; } BigInteger & BigInteger::operator*= (const BigInteger & second) { BigInteger result = (*this) * second; *this = result; return *this; } string BigInteger::str_repr() const { string res = vector2string(); if(res != "0") { if(_positive) res = "+" + res; else res = "-" + res; } return res; } inline int BigInteger::string2int(string & str) const { stringstream ss; ss << str; int n; ss >> n; return n; } inline string BigInteger::int2string(int val) const { stringstream ss; ss << val; return ss.str(); } void BigInteger::string2vector(string & str) { _vec.clear(); if(str.empty()) { _vec.push_back(0); return; } int idx = (int)str.size(); while(idx > 0) { int start = idx - UNIT_LEN; if(start < 0) start = 0; string substr = str.substr(start, idx - start); int val = string2int(substr); _vec.push_back(val); idx = start; } } string BigInteger::vector2string() const { if(_vec.empty()) return "0"; string res; for(int i=0; i<_vec.size()-1; i++) { int val = _vec[i]; string str = int2string(val); if(str.length() < UNIT_LEN) { string complement(UNIT_LEN - str.length(), '0'); str = complement + str; } res = str + res; } int val = _vec[_vec.size()-1]; string str = int2string(val); res = str + res; return res; } BigInteger operator+ (const BigInteger & first, const BigInteger & second) { BigInteger result; if(first._positive && second._positive) { result = unsign_plus(first, second); result._positive = true; } else if(first._positive && !second._positive) { if(unsign_greater_equal(first, second)) { result = unsign_minus(first, second); result._positive = true; } else { result = unsign_minus(second, first); result._positive = false; } } else if(!first._positive && second._positive) { if(unsign_greater(first, second)) { result = unsign_minus(first, second); result._positive = false; } else { result = unsign_minus(second, first); result._positive = true; } } else { result = unsign_plus(first, second); result._positive = false; } return result; } BigInteger operator- (const BigInteger & first, const BigInteger & second) { BigInteger result; if(first._positive && !second._positive) { result = unsign_plus(first, second); result._positive = true; } else if(first._positive && second._positive) { if(unsign_greater_equal(first, second)) { result = unsign_minus(first, second); result._positive = true; } else { result = unsign_minus(second, first); result._positive = false; } } else if(!first._positive && !second._positive) { if(unsign_greater(first, second)) { result = unsign_minus(first, second); result._positive = false; } else { result = unsign_minus(second, first); result._positive = true; } } else { result = unsign_plus(first, second); result._positive = false; } return result; } BigInteger operator* (const BigInteger & first, const BigInteger & second) { if((first._vec.size() == 1 && first._vec[0] == 0) || (second._vec.size() == 1 && second._vec[0] == 0)) return BigInteger(0); BigInteger result; result = unsign_multiply(first, second); if(first._positive == second._positive) result._positive = true; else result._positive = false; return result; } BigInteger operator/ (const BigInteger & first, const BigInteger & second) { if(first._vec.size() == 1 && first._vec[0] == 0) { return BigInteger(0); } BigInteger res = unsign_divide(first, second); if(first._positive == second._positive) res._positive = true; else res._positive = false; return res; } BigInteger operator% (const BigInteger & first, const BigInteger & second) { if(first._vec.size() == 1 && first._vec[0] == 0) return BigInteger(0); BigInteger res = unsign_mod(first, second); if(first._positive == second._positive) res._positive = true; else res._positive = false; return res; } istream & operator>> (istream & in, BigInteger & num) { string str; in >> str; num = BigInteger(str); return in; } ostream & operator<< (ostream & out, const BigInteger & num) { string str = num.str_repr(); out << str; return out; } BigInteger unsign_plus(const BigInteger & first, const BigInteger & second) { BigInteger result; size_t m = first._vec.size(); size_t n = second._vec.size(); int max_one = (m > n)?m:n; result._vec.resize(max_one + 1); int carry = 0; int idx = 0; while(idx < m || idx < n) { int a = 0, b = 0; if(idx < m) a = first._vec[idx]; if(idx < n) b = second._vec[idx]; long long int tmp = a + b + carry; result._vec[idx] = tmp % BigInteger::MAX_UNIT; carry = (int)(tmp / (long long int)BigInteger::MAX_UNIT); idx ++; } result._vec[idx] = carry;; idx = result._vec.size()-1; while(idx > 0 && result._vec[idx] == 0) idx --; result._vec.resize(idx + 1); return result; } //We assume the first argument is greater than the second one BigInteger unsign_minus(const BigInteger & first, const BigInteger & second) { BigInteger result; size_t m = first._vec.size(); size_t n = second._vec.size(); result._vec.resize(m + 1); int carry = 0; int idx = 0; while(idx < m) { int a = first._vec[idx], b = 0; if(idx < n) b = second._vec[idx]; long long int tmp = b + carry; if(a >= tmp) { result._vec[idx] = (int)(a - tmp); carry = 0; } else { a = a + BigInteger::MAX_UNIT; result._vec[idx] = (int)(a - tmp); carry = 1; } idx ++; } idx = (int)(result._vec.size() - 1); while(idx > 0 && result._vec[idx] == 0) idx --; result._vec.resize(idx + 1); return result; } BigInteger unsign_multiply (const BigInteger & first, const BigInteger & second) { BigInteger result; size_t m = first._vec.size(); size_t n = second._vec.size(); result._vec.resize(m + n); fill(result._vec.begin(), result._vec.end(), 0); for(int i=0; i<first._vec.size(); i++) { for(int j=0; j<second._vec.size(); j++) { int pos = i + j; long long int tmp = (long long int)first._vec[i] * (long long int)second._vec[j]; while(tmp > 0) { tmp += result._vec[pos]; result._vec[pos] = tmp % BigInteger::MAX_UNIT; tmp = tmp / BigInteger::MAX_UNIT; pos ++; } } } int idx = (int)result._vec.size() - 1; while(idx > 0 && result._vec[idx] == 0) idx --; result._vec.resize(idx + 1); return result; } //This is a naive function for divide. There must be some other faster algorithms for division. BigInteger unsign_divide (const BigInteger & first, const BigInteger & second) { if(second._vec.size() == 1 && second._vec[0] == 0) exit(1); if((first._vec.size() == 1 && first._vec[0] == 0) || unsign_less(first, second)) return BigInteger(0); else { BigInteger res(0); BigInteger tmp(first); while(unsign_greater_equal(tmp, second)) { tmp = unsign_minus(tmp, second); res += 1; } if(first._positive == second._positive) res._positive = true; else res._positive = false; return res; } } //This is a naive function for mod. There must be some other faster algorithms for mod. BigInteger unsign_mod (const BigInteger & first, const BigInteger & second) { if(second._vec.size() == 1 && second._vec[0] == 0) exit(1); if(first._vec.size() == 1 && first._vec[0] == 0) return BigInteger(0); if(unsign_less(first, second)) { BigInteger res(first); return res; } else { BigInteger tmp(first); while(unsign_greater_equal(tmp, second)) tmp = unsign_minus(tmp, second); return tmp; } } bool operator> (const BigInteger & first, const BigInteger & second) { if(first._positive && !second._positive) return true; else if(first._positive && second._positive) return unsign_greater(first, second); else if(!first._positive && second._positive) return false; else return unsign_less(first, second); } bool operator< (const BigInteger & first, const BigInteger & second) { if(first._positive && !second._positive) return false; else if(first._positive && second._positive) return unsign_less(first, second); else if(!first._positive && second._positive) return true; else return unsign_greater(first, second); } bool operator>= (const BigInteger & first, const BigInteger & second) { return !(first < second); } bool operator<= (const BigInteger & first, const BigInteger & second) { return !(first > second); } bool operator== (const BigInteger & first, const BigInteger & second) { if(first._positive != second._positive) return false; else return unsign_equal(first, second); } bool unsign_greater (const BigInteger & first, const BigInteger & second) { if(first._vec.size() > second._vec.size()) return true; else if(first._vec.size() < second._vec.size()) return false; else { for(int i=first._vec.size()-1; i>=0; i--) { if(first._vec[i] > second._vec[i]) return true; else if(first._vec[i] < second._vec[i]) return false; } return false; } } bool unsign_less (const BigInteger & first, const BigInteger & second) { if(first._vec.size() < second._vec.size()) return true; else if(first._vec.size() > second._vec.size()) return false; else { for(int i=first._vec.size()-1; i>=0; i--) { if(first._vec[i] < second._vec[i]) return true; else if(first._vec[i] > second._vec[i]) return false; } return false; } } bool unsign_greater_equal (const BigInteger &first, const BigInteger &second) { return !unsign_less(first, second); } bool unsign_less_equal (const BigInteger & first, const BigInteger & second) { return !unsign_greater(first, second); } bool unsign_equal (const BigInteger & first, const BigInteger & second) { if(first._vec.size() != second._vec.size()) return false; else { for(int i=0; i<first._vec.size(); i++) { if(first._vec[i] != second._vec[i]) return false; } return true; } } unsigned int BigInteger::MAX_UNIT = 100000000; unsigned int BigInteger::UNIT_LEN = 8; BigInteger pow(const BigInteger & first, int n) { if(n == 0) return BigInteger(1); else if(n == 1) return first; else if(n % 2) return first * pow(first, n-1); else { BigInteger res = pow(first, n/2); return res * res; } } int main(int argc, const char * argv[]) { string str; int n; while(cin >> str >> n) { int len = 0; size_t index = str.find('.'); if(index != string::npos) { len = str.size() - index - 1; str = str.substr(0, index) + str.substr(index+1); } BigInteger result = pow(BigInteger(str), n); string res = result.str_repr(); res = res.substr(1); len = len * n; if(res.size() > len) { if(len != 0) { int pos = res.size() - len; res = res.substr(0, pos) + '.' + res.substr(pos); } else { cout << res << endl; return 0; } } else { len = len - res.size(); res = '.' + string(len, '0') + res; } int idx = res.size() - 1; while(idx > 0 && res[idx] == '0') idx --; if(idx == 0) res = "0"; else if(res[idx] == '.') res = res.substr(0, idx); else res = res.substr(0, idx + 1); cout << res << endl; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator