| ||||||||||
| 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