#include <iostream>
#include <map>

using std::map;
using std::ostream;

template<typename base_t, typename exp_t>
const base_t power(base_t x, exp_t n) {
        base_t r(1);
        while (n > exp_t(1)) {
                if (n % exp_t(2) == exp_t(1)) r *= x;
                n /= exp_t(2);
                x *= x;
        }
        return r*x;
}


template<typename base_t, typename exp_t>
class bignum_t {
        public:
                virtual ~bignum_t() {}
                bignum_t() : factors() {}

                bignum_t(const base_t & p) : factors() {
                        // FIXME: Needs to be factored first!!!
                        factors[p] = exp_t(1);
                }

                bignum_t(const base_t & p, const exp_t & e) : factors() {
                        // FIXME: Needs to be factored first!!!
                        factors[p] = e;
                }

                bignum_t(const bignum_t & rhs) : factors(rhs.factors) {}

                bignum_t & operator = (const base_t & p) {
                        // FIXME: Needs to be factored first!!!
                        if (this->factors.size()) this->factors.clear();
                        factors[p] = exp_t(1);
                        return *this;
                }

                bignum_t & operator = (const bignum_t & rhs) {
                        if (this->factors.size()) this->factors.clear();
                        this->factors = rhs.factors;
                        return *this;
                }

                friend ostream & operator << (ostream & lhs, \
                                              const bignum_t & rhs) {

                        for (typename map<base_t,exp_t>::const_iterator it=rhs.factors.begin();\
                               it != rhs.factors.end(); it++) {
                                if (it != rhs.factors.begin())
                                        lhs << "*";
                                lhs << it->first;
                                //if (it->second > exp_t(1) || it->second < exp_t(-1))
                                        lhs << "^" << it->second;
                        }
                        return lhs;
                }


                operator int32_t () {
                        int32_t numerator = 1, denominator = 1;
                        for (typename map<base_t,exp_t>::const_iterator it = this->factors.begin(); \
                                it != this->factors.end(); it++) {
                                if (it->second > 0)
                                        numerator *= (int32_t) power(it->first, it->second);
                                else
                                        denominator *= (int32_t) power(it->first, it->second);
                        }
                        return numerator / denominator;
                }

                operator double () {
                        double numerator = 1.0, denominator = 1.0;
                        for (typename map<base_t,exp_t>::const_iterator it = this->factors.begin(); \
                                it != this->factors.end(); it++) {
                                        if (it->second > 0)
                                                numerator *= (double) power(it->first, it->second);
                                        else
                                                denominator *= (double) power(it->first, it->second);
                        }
                        return numerator / denominator;
                }

                const bignum_t operator ~ () const {
                        bignum_t temp(*this);
                        for (typename map<base_t, exp_t>::iterator it = temp.factors.begin(); \
                                                it != temp.factors.end(); it++)
                                it->second *= exp_t(-1);
                        return temp;
                }

                const bignum_t & operator ^ (const base_t & rhs) const {
                        bignum_t temp(*this);
                        for (typename map<base_t, exp_t>::iterator it = temp.factors.begin(); \
                                it != temp.factors.end(); it++)
                                it->second *= rhs;
                        return temp;
                }

                const bignum_t operator / (const bignum_t & rhs) const {
                        return *this * ~rhs;
                }

                const bignum_t operator + (bignum_t addend2) const {
                        bignum_t res, temp, addend1(*this);
                        exp_t diff;

                        // First we copy all the common factors into temp
                        // so that our evaluation and subsequent factoring
                        // is minimized.
                        for (unsigned int j = 0; j < 2; j++) {
                                for (typename map<base_t, exp_t>::iterator it1 = \
                                     j ? addend2.factors.begin() : addend1.factors.begin() \
                                     , it2; it1 != addend1.factors.end(); it1++) {
                                        it2 = j ? addend1[it1->first] : addend2[it1->first];
                                        diff = exp_t(0);
                                        if (it1->second > 0 && it2->second > 0) {
                                                diff = (it1->second < it2->second) ? it1->second : it2->second;
                                        } else if (it1->second < 0 && it1->second < 0) {
                                                diff = (it1->second > it2->second) ? it1->second : it2->second;
                                                diff *= exp_t(-1);
                                        }
                                        if (diff != 0) {
                                                temp[it1->first] = diff;
                                                it1->second -= diff;
                                                it2->second -= diff;
                                        }
                                }
                        }

                        // Now we find the lcm and remove it from the addends
                        // and place it in the result

                        // Now we evaluate the numerator

                        // Now we just need to factor the numerator
                        // which is all the factors with positive exponents.
                        // ... Factorization goes here ...

                        // Finally we multiply what we originally factored
                        // out and return
                        return res * temp;
                }

                const bignum_t operator * (const bignum_t & rhs) const {
                        bignum_t temp(*this);

                        for (typename map<base_t, exp_t>::const_iterator it = \
                              rhs.factors.begin(); it != rhs.factors.end(); it++)
                                if ( ((bignum_t &) rhs).factors  [it->first])
                                        temp.factors[it->first] = it->second + \
                                               ((bignum_t &) *this).factors[it->first];

                        return temp;
                }

        protected:
                map<base_t, exp_t> factors;

};

typedef bignum_t<uint32_t, int32_t> bignum32;
typedef bignum_t<uint64_t, int32_t> bignum64;

using std::cout;
using std::endl;

int main() {

        bignum32 b2(5,2);
        bignum32 b(5,2);
        bignum32 b3 = b * b2;

        cout << (double) b3 << endl;

/*
        bignum32 b, b2, b3;

        srand(time(NULL));

        for (unsigned int i = 0; i < 1000; i++) {
                b  = rand() % 1000 + 500;
                b2 = rand() % 500  + 1;
                b3 = b / b2;
                //std::cout << (int32_t) (b3) << std::endl << std::endl;
        }
*/

        return 0;

}