Pagini recente » Cod sursa (job #722743) | Cod sursa (job #2150614) | Cod sursa (job #1878759) | Cod sursa (job #1390956) | Cod sursa (job #865005)
Cod sursa(job #865005)
#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()
{
}