Cod sursa(job #822871)

Utilizator axnsanCristi Vijdea axnsan Data 24 noiembrie 2012 10:00:00
Problema Patrate2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
//#include <iostream>
#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()
{
}