Cod sursa(job #865005)

Utilizator stoicatheoFlirk Navok stoicatheo Data 25 ianuarie 2013 22:23:38
Problema Patrate2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <fstream>
#include <string>
#include <stdint.h>
#include <vector>
#include <algorithm>
using namespace std;
class BigNum
{
public:
    BigNum();
    explicit BigNum(std::vector<uint32_t> &Digits);
    std::string toDecimal() const;
 
    unsigned numDigits() const;
    friend std::ostream& operator<<(std::ostream& out, const BigNum& number);
    BigNum& operator*=(const uint32_t &rhs);
    bool isZero() const;
    ~BigNum();
 
private:
    std::vector<uint32_t> digits;
    static uint32_t _divideBy10(std::vector<uint32_t>&);
};
std::ostream& operator<<(std::ostream& out, const BigNum& number);
BigNum Pow2(uint32_t n)
{
    int e = n/32;
    vector<uint32_t> vec(e+1, 0);
    vec.push_back(1<<(n%32));
    vec[0] = e+1;
    return BigNum(vec);
}
int main() 
{
    unsigned N;
    ifstream f("patrate2.in");
    f >> N;
    BigNum big(Pow2(N*N));
    for (unsigned i = 2;i <= N;++i)
        big *= i;
 
    ofstream g("patrate2.out");
    g << big << endl;
}
BigNum& BigNum::operator*=(const uint32_t &rhs)
{
    if (this->isZero() || rhs == 0)
    {
        digits[0] = 0;
        return *this;
    }
    uint32_t carry = 0;
    for (unsigned i = 1;i <= numDigits(); ++i)
    {
        uint64_t M = (uint64_t(digits[i]) * rhs) + carry;
        carry = uint32_t(M / 0x100000000);
        digits[i] = uint32_t(M % 0x100000000);
    }
    if (carry > 0)
    {
        ++digits[0];
        if (digits.size() - 1 < digits[0])
            digits.push_back(carry);
        else digits[digits[0]] = carry;
    }
    return *this;
}
std::string BigNum::toDecimal() const
{
    std::vector<uint32_t> number(this->digits);
    std::string ret;
    int n = 0;
    do {
        int digit = _divideBy10(number);
        ret.push_back(digit + '0');
    } while(number[0] != 0);
    std::reverse(ret.begin(), ret.end());
    return ret;
}
std::ostream& operator<<(std::ostream& out, const BigNum& number)
{
    out << number.toDecimal();
    return out;
}
uint32_t BigNum::_divideBy10(std::vector<uint32_t>& number)
{
    uint32_t r(0), d;
    uint64_t t;
    for (uint32_t i = number.front(); i >= 1; --i) {
        t = number[i] + r*0x100000000;
        d = uint32_t(t / 10);
        r = uint32_t(t % 10);
        number[i] = d;
    }
    while (number[0] > 0 && number[number[0]] == 0)
        --number[0];
 
    return r;
}
BigNum::BigNum()
{
    digits.push_back(0);
}
BigNum::BigNum(std::vector<uint32_t> &Digits)
{
    if (!Digits.empty() && Digits[0] <= Digits.size()-1)
        this->digits = Digits;
    else this->digits.push_back(0);
}
inline unsigned BigNum::numDigits() const
{
    if (!digits.empty())
        return digits.front();
    return 0;
}
inline bool BigNum::isZero() const
{
    return (digits.empty() || digits[0] == 0);
}
BigNum::~BigNum()
{
}