Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

代码:欢迎来我博客http://hodgezhang.sinaapp.com/?p=184

Posted by bikeboy at 2013-01-27 11:34:39 on Problem 1001
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator