fork download

copy

#include <algorithm>
#include <array>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <memory>
#include <string>
#include <utility>
 
using namespace std;
 
class RPG;
class SimpleRPG;
class RBG;
class SimpleRBG;
class HA;
class SHA1;
class Sieve;
class PT;
class MRBPT;
class BigMath;
class BigInt;
class BitField;
class BitInputStream;
template <class X> class PrimitiveBitInputStream;
template <class X> class Pool;
template <class X> class ExArray;
template <class X> class PrimitiveExArray;
template <class X> class ClassObjectExArray;
 
class RPG {
public:
    virtual BigInt generatePrime(const unsigned int& len) = 0;
protected:
	static bool findSmallPrimeFactor(const BigInt& num);
};
 
class SimpleRPG : public RPG {
public:
	SimpleRPG();
	virtual BigInt generatePrime(const unsigned int& len);
protected:
	shared_ptr<RBG> rbg;
	shared_ptr<PT> pt;
	SimpleRPG(const SimpleRPG& simple_rpg);
	SimpleRPG& operator =(const SimpleRPG& simple_rpg);
};
 
class RBG {
public:
	virtual bool generateBit() = 0;
};
 
class SimpleRBG : public RBG {
public:
	SimpleRBG();
	virtual bool generateBit();
protected:
	shared_ptr<BitField> hash;
	unsigned int pos;
	SimpleRBG(const SimpleRBG& simple_rbg);
	SimpleRBG& operator =(const SimpleRBG& simple_rbg);
};
 
class HA {
public:
	virtual shared_ptr<BitField> computeHash(const shared_ptr<BitInputStream>& msg) = 0;
};
 
class SHA1 : public HA {
public:
	SHA1();
	virtual shared_ptr<BitField> computeHash(const shared_ptr<BitInputStream>& msg);
protected:
	typedef unsigned long (*FUNCTION)(const unsigned long& x, const unsigned long& y, const unsigned long& z);
	SHA1(const SHA1& sha1);
	SHA1& operator =(const SHA1& sha1);
	static const FUNCTION FUNCTIONS[4];
	static const unsigned long K[4];
	static const unsigned long INITIAL_HASH_VALUES[5];
	static unsigned long ch(const unsigned long& x, const unsigned long& y, const unsigned long& z);
	static unsigned long parity(const unsigned long& x, const unsigned long& y, const unsigned long& z);
	static unsigned long maj(const unsigned long& x, const unsigned long& y, const unsigned long& z);
};
 
class Sieve {
public:
	unsigned int getNextPrime(const unsigned int& prev_num);
	static Sieve instance;
protected:
	shared_ptr<PrimitiveExArray<bool> > tab;
	Sieve();
};
 
class PT {
public:
	virtual bool isPrime(const BigInt& p) = 0;
};
 
class MRBPT : public PT {
public:
	MRBPT();
	virtual bool isPrime(const BigInt& p);
protected:
	MRBPT(const MRBPT& mrbpt);
	MRBPT& operator =(const MRBPT& mrbpt);
};
 
class BigMath {
public:
	static BigInt power(const BigInt& base, const BigInt& exp);
	static BigInt power(const BigInt& base, const BigInt& exp, const BigInt& nrm);
	static BigInt gcd(const BigInt& a, const BigInt& b);
	static BigInt lcm(const BigInt& a, const BigInt& b);
	static BigInt inverse(const BigInt& num, const BigInt& nrm);
protected:
	BigMath();
};
 
template <class X> 
class ExArray {
public:
	virtual X& operator [](const unsigned int& i) = 0;
	virtual X& at(const unsigned int& i) = 0;
	virtual X& last() = 0;
	virtual unsigned int getSize() const = 0;
	virtual bool isEmpty() const = 0;
	virtual void push(const X& x) = 0;
	virtual void pop() = 0;
	virtual void clear() = 0;
	virtual void resize(const unsigned int& sz) = 0;
};
 
template <class X> 
class PrimitiveExArray : public ExArray<X> {
public:
	PrimitiveExArray(const unsigned int& sz = 0);
	PrimitiveExArray(const PrimitiveExArray& a);
	virtual ~PrimitiveExArray();
	PrimitiveExArray& operator =(const PrimitiveExArray& a);
	virtual X& operator [](const unsigned int& i);
	virtual X& at(const unsigned int& i);
	virtual X& last();
	virtual unsigned int getSize() const;
	virtual bool isEmpty() const;
	virtual void push(const X& x);
	virtual void pop();
	virtual void clear();
	virtual void resize(const unsigned int& sz);
protected:
	X* buf;
	unsigned int buf_sz;
	unsigned int sz;
};
 
template <class X> 
class ClassObjectExArray : public ExArray<X> {
public:
	ClassObjectExArray(const unsigned int& sz = 0);
	ClassObjectExArray(const ClassObjectExArray& a);
	virtual ~ClassObjectExArray();
	ClassObjectExArray& operator =(const ClassObjectExArray& a);
	virtual X& operator [](const unsigned int& i);
	virtual X& at(const unsigned int& i);
	virtual X& last();
	virtual unsigned int getSize() const;
	virtual bool isEmpty() const;
	virtual void push(const X& x);
	virtual void pop();
	virtual void clear();
	virtual void resize(const unsigned int& sz);
protected:
	X* buf;
	unsigned int buf_sz;
	unsigned int sz;
};
 
template <class X> 
class Pool {
public:
	class Ptr {
	public:
		Ptr(Pool* pool);
		Ptr(const Ptr& ptr);
		virtual ~Ptr();
		Ptr& operator =(const Ptr& ptr);
		X& operator *() const;
		X* operator ->() const;
		X* get() const;
	protected:
		Pool* pool;
		pair<X*, unsigned int*> x_cnt;
		void release();
	};
	virtual ~Pool();
protected:
	PrimitiveExArray<pair<X*, unsigned int*> > xa;
	pair<X*, unsigned int*> get();
	void putBack(const pair<X*, unsigned int*>& x_cnt);
	friend Ptr;
};
 
class BigInt {
public:
	BigInt();
	BigInt(const int& num);
	BigInt(const string& str, const unsigned int& base = 10);
	BigInt(const int& sign, const BitField& fld);
	BigInt(const BigInt& num);
	BigInt operator -() const;
	BigInt operator +(const BigInt& ade) const;
	BigInt operator -(const BigInt& sub) const;
	BigInt operator *(const BigInt& mer) const;
	BigInt operator /(const BigInt& dsr) const;
	BigInt operator %(const BigInt& nrm) const;
	BigInt operator <<(const size_t& num) const;
	BigInt operator >>(const size_t& num) const;
	BigInt& operator =(const BigInt& num);
	BigInt& operator +=(const BigInt& ade);
	BigInt& operator -=(const BigInt& sub);
	BigInt& operator *=(const BigInt& mer);
	BigInt& operator /=(const BigInt& dsr);
	BigInt& operator %=(const BigInt& nrm);
	BigInt& operator <<=(const unsigned int& num);
	BigInt& operator >>=(const unsigned int& num);
	BigInt& operator ++();
	BigInt operator ++(int);
	BigInt& operator --();
	BigInt operator --(int);
	bool operator ==(const BigInt& num) const;
	bool operator <(const BigInt& num) const;
	bool operator >(const BigInt& num) const;
	bool operator !=(const BigInt& num) const;
	bool operator <=(const BigInt& num) const;
	bool operator >=(const BigInt& num) const;
	BigInt abs() const;
	bool isZero() const;
	int getSign() const;
	bool getLSBit() const;
	unsigned long getLSLong() const;
	void setInt(const int& num);
	string toString(const unsigned int& base = 10) const;
	unsigned int getLength() const;
protected:
	class BFPtr : public Pool<BitField>::Ptr {
	public:
		BFPtr();
		BFPtr(const unsigned long& num);
		BFPtr(const BitField& fld);
	protected:
		static Pool<BitField> pool;
	};
	int sign;
	BFPtr fld;
	BigInt(const int& sign, const BFPtr& fld);
	static const unsigned int LONG_LEN;
	static BFPtr add(const BFPtr& age, const BFPtr& ade);
	static BFPtr subtract(const BFPtr& min, const BFPtr& sub);
	static BFPtr multiply(const BFPtr& mca, const BFPtr& mer);
	static pair<BFPtr, BFPtr> divide(const BFPtr& dde, const BFPtr& dsr);
	static unsigned int digitToNumber(const char& dig);
	static char numberToDigit(const unsigned int& num);
};
 
class BitField {
public:
	class LongInputStream {
	public:
		LongInputStream(const BitField* fld);
		bool isEOF() const;
		unsigned long getLong();
	protected:
		const BitField* fld;
		unsigned int end;
		unsigned int cur;
		unsigned int low_len;
		unsigned int high_len;
		unsigned long low_mask;
		unsigned long high_mask;
		unsigned long rem;
		unsigned long num;
	};
	class LongOutputStream {
	public:
		LongOutputStream(BitField* fld);
		virtual ~LongOutputStream();
		void putLong(const unsigned long& num);
		void flush();
	protected:
		BitField* fld;
		unsigned int cur;
		unsigned int low_len;
		unsigned int high_len;
		unsigned long low_mask;
		unsigned long high_mask;
		unsigned long high_buf;
		bool bufed;
	};
	class ReverseLongInputStream {
	public:
		ReverseLongInputStream(const BitField* fld);
		bool isEOF() const;
		unsigned long getLong();
	protected:
		const BitField* fld;
		unsigned int end;
		unsigned int cur;
		unsigned int low_len;
		unsigned int high_len;
		unsigned long low_mask;
		unsigned long high_mask;
		unsigned long rem;
		unsigned long num;
	};
	class ReverseLongOutputStream {
	public:
		ReverseLongOutputStream(BitField* fld);
		virtual ~ReverseLongOutputStream();
		void putLong(const unsigned long& num);
		void flush();
	protected:
		BitField* fld;
		unsigned int low_len;
		unsigned int high_len;
		unsigned long low_mask;
		unsigned long high_mask;
		unsigned long low_buf;
		bool bufed;
	};
	BitField();
	BitField(const unsigned long& num);
	BitField(const BitField& fld);
	virtual ~BitField();
	BitField& operator =(const BitField& fld);
	unsigned int getLength() const;
	bool isEmpty() const;
	bool isZero() const;
	bool getBit(const unsigned int& pos) const;
	bool getLSBit() const;
	bool getMSBit() const;
	unsigned long getLong(const unsigned int& ls_pos) const;
	unsigned long getLSLong() const;
	void setBit(const unsigned int& pos, const bool& bit);
	void pushMS(const bool& bit);
	template <class X> void pushMS(const X& x);
	void pushLS(const bool& bit);
	template <class X> void pushLS(const X& x);
	void setLong(const unsigned long& num);
	void shift(const int& num);
	void trim();
	void clear();
	int compare(const BitField& fld) const;
	string toString() const;
	bool isPowerOf2() const;
	BitField getSubfield(const unsigned int& ls_pos, const unsigned int& len) const;
protected:
	unsigned char* buf;
	unsigned int buf_sz;
	int beg;
	unsigned int len;
	void extendIfNecessary(const int& len);
	friend LongInputStream;
	friend LongOutputStream;
	friend ReverseLongInputStream;
	friend ReverseLongOutputStream;
};
 
class BitInputStream {
public:
	virtual bool getBit() = 0;
	virtual bool isEOF() = 0;
};
 
template <class X> 
class PrimitiveBitInputStream : public BitInputStream {
public:
	PrimitiveBitInputStream(const X& x);
	virtual bool getBit();
	virtual bool isEOF();
protected:
	X x;
	unsigned int pos;
	PrimitiveBitInputStream(const PrimitiveBitInputStream& sbin);
	PrimitiveBitInputStream& operator =(const PrimitiveBitInputStream& sbin);
};
 
template <class X> X rotateLeft(const X& x, const unsigned int& n, const unsigned int& w = (sizeof(X) << 3));
 
bool RPG::findSmallPrimeFactor(const BigInt& num) {
	bool res = false;
	unsigned int end = (num.getLength() * num.getLength()) >> 6;
	for (unsigned int prime = 3; prime < end; prime = Sieve::instance.getNextPrime(prime)) {
		if ((num % prime).isZero()) {
			res = true;
			break;
		}
	}
	return res;
}
 
SimpleRPG::SimpleRPG() : rbg(new SimpleRBG), pt(new MRBPT) {}
 
BigInt SimpleRPG::generatePrime(const unsigned int& len) {
	BigInt num;
	bool found = false;
	while (!found) {
		BitField fld;
		fld.pushMS(true);
		for (unsigned int i = 0; i < len - 2; i++) 
			fld.pushMS(this->rbg->generateBit());
		fld.pushMS(true);
		for (num = BigInt(1, fld); num.getLength() == len; num += 2) {
			if (!findSmallPrimeFactor(num) && this->pt->isPrime(num)) {
				found = true;
				break;
			}
		}
	}
	return num;
}
 
SimpleRBG::SimpleRBG() : pos(160) {
	unsigned long long t = time(nullptr);
	unsigned long long c = clock();
	srand((t >> 32) ^ (t & 0xffffffff) ^ (c >> 32) ^ (c & 0xffffffff));
}
 
bool SimpleRBG::generateBit() {
	if (this->pos >= 160) {
		shared_ptr<HA> ha(new SHA1);
		this->hash = ha->computeHash(shared_ptr<BitInputStream>(new PrimitiveBitInputStream<int>(rand())));
		this->pos = 0;
	}
	bool res = this->hash->getBit(32 * (this->pos >> 5) + (32 - 1 - (this->pos & 0x1F)));
	this->pos++;
	return res;
}
 
const SHA1::FUNCTION SHA1::FUNCTIONS[4] = {
	ch, 
	parity, 
	maj, 
	parity, 
};
 
const unsigned long SHA1::K[4] = {
	0x5a827999, 
	0x6ed9eba1, 
	0x8f1bbcdc, 
	0xca62c1d6, 
};
 
const unsigned long SHA1::INITIAL_HASH_VALUES[5] = {
	0x67452301, 
	0xefcdab89, 
	0x98badcfe, 
	0x10325476, 
	0xc3d2e1f0, 
};
 
SHA1::SHA1() {}
 
shared_ptr<BitField> SHA1::computeHash(const shared_ptr<BitInputStream>& msg) {
	shared_ptr<array<unsigned long, 5> > hash(new array<unsigned long, 5>);
	copy(INITIAL_HASH_VALUES, INITIAL_HASH_VALUES + 5, &hash->front());
	shared_ptr<array<unsigned long, 16> > block(new array<unsigned long, 16>);
	shared_ptr<array<unsigned long, 80> > sche(new array<unsigned long, 80>);
	unsigned long long len = 0;
	bool put_end = false;
	bool put_len = false;
	while (!put_len) {
		block->fill(0);
		unsigned int block_pos = 0;
		for (; block_pos < 512 && !msg->isEOF(); block_pos++) {
			block->at(block_pos >> 5) |= (msg->getBit() == true ? 1 : 0) << (32 - 1 - (block_pos & 0x1f));
			len++;
		}
		if (block_pos < 512) {
			if (!put_end) {
				block->at(block_pos >> 5) |= 1 << (32 - 1 - (block_pos & 0x1f));
				block_pos++;
				put_end = true;
			}
			if (block_pos + 64 <= 512) {
				block->at(14) = len >> 32;
				block->at(15) = len & 0xffffffff;
				put_len = true;
			}
		}
		for (unsigned int i = 0; i < 80; i++) {
			if (i < 16) sche->at(i) = block->at(i);
			else sche->at(i) = rotateLeft(
				sche->at(i - 3) ^ 
				sche->at(i - 8) ^ 
				sche->at(i - 14) ^ 
				sche->at(i - 16), 1);
		}
		unsigned long a = hash->at(0);
		unsigned long b = hash->at(1);
		unsigned long c = hash->at(2);
		unsigned long d = hash->at(3);
		unsigned long e = hash->at(4);
		for (unsigned int i = 0; i < 80; i++) {
			unsigned long t =
				rotateLeft(a, 5) + 
				FUNCTIONS[i / 20](b, c, d) + 
				e + 
				K[i / 20] + 
				sche->at(i);
			e = d;
			d = c;
			c = rotateLeft(b, 30);
			b = a;
			a = t;
		}
		hash->at(0) += a;
		hash->at(1) += b;
		hash->at(2) += c;
		hash->at(3) += d;
		hash->at(4) += e;
	}
	shared_ptr<BitField> res(new BitField);
	for (unsigned int i = 0; i < 5; i++) res->pushMS(hash->at(i));
	return res;
}
 
unsigned long SHA1::ch(const unsigned long& x, const unsigned long& y, const unsigned long& z) {
	return (x & y) ^ (~x & z);
}
 
unsigned long SHA1::parity(const unsigned long& x, const unsigned long& y, const unsigned long& z) {
	return x ^ y ^ z;
}
 
unsigned long SHA1::maj(const unsigned long& x, const unsigned long& y, const unsigned long& z) {
	return (x & y) ^ (x & z) ^ (y & z);
}
 
unsigned int Sieve::getNextPrime(const unsigned int& prev_num) {
	unsigned int res;
	for (;;) {
		{
			unsigned int i = prev_num + 1;
			for (; i < this->tab->getSize(); i++) {
				if (this->tab->at(i) == true) {
					res = i;
					break;
				}
			}
			if (i < this->tab->getSize()) break;
		}
		unsigned int new_sz = this->tab->getSize() << 1;
		if (new_sz == 0) new_sz = 1;
		for (unsigned int i = this->tab->getSize(); i < new_sz; i++) 
			this->tab->push(true);
		for (unsigned int i = 0; i < this->tab->getSize(); i++) {
			if (this->tab->at(i) == true) {
				for (unsigned int j = i + i; j < this->tab->getSize(); j += i) 
					this->tab->at(j) = false;
			}
		}
	}
	return res;
}
 
Sieve Sieve::instance;
 
Sieve::Sieve() : tab(new PrimitiveExArray<bool>) {
	this->tab->push(false);
	this->tab->push(false);
}
 
MRBPT::MRBPT() {}
 
bool MRBPT::isPrime(const BigInt& p) {
	bool res = true;
	if (p == 1) res = false;
	else if (p == 2) res = true;
	else if (p.getLSBit() == false) res = false;
	else {
		BigInt o = p - 1;
		BigInt q = o;
		BigInt k(1);
		while (q.getLSBit() == false) {
			q >>= 1;
			k++;
		}
		BigInt cnt(3072 / p.getLength());
		if (cnt == 0) cnt = 1;
		BigInt a(2);
		BigInt gap(p / cnt);
		if (gap.isZero()) gap = 1;
		for (; a < p; a += gap) {
			BigInt b = BigMath::power(a, q, p);
			if (b != 1 && b != o) {
				BigInt i(1);
				for (; i < k; i++) {
					b = (b * b) % p;
					if (b == o) break;
				}
				if (i == k) {
					res = false;
					break;
				}
			}
		}
	}
	return res;
}
 
BigInt BigMath::power(const BigInt& base, const BigInt& exp) {
	BigInt res;
	if (base.isZero()) res = BigInt(0);
	else if (exp.isZero()) res = BigInt(1);
	else if (exp < 0) res = BigInt(1) / power(base, -exp);
	else {
		res.setInt(1);
		BigInt coef = base;
		for (BigInt exp2 = exp;;) {
			if (exp2.getLSBit()) res *= coef;
			exp2 >>= 1;
			if (exp2.isZero()) break;
			coef *= coef;
		}
	}
	return res;
}
 
BigInt BigMath::power(const BigInt& base, const BigInt& exp, const BigInt& nrm) {
	BigInt res;
	if (base.isZero()) res = BigInt(0);
	else if (exp.isZero()) res = BigInt(1);
	else if (exp < 0) res = (BigInt(1) / power(base, -exp)) % nrm;
	else {
		res.setInt(1);
		BigInt coef = base % nrm;
		for (BigInt exp2 = exp;;) {
			if (exp2.getLSBit()) res = (res * coef) % nrm;
			exp2 >>= 1;
			if (exp2.isZero()) break;
			coef = (coef * coef) % nrm;
		}
	}
	return res;
}
 
BigInt BigMath::gcd(const BigInt& a, const BigInt& b) {
	BigInt c(a.abs()), d(b.abs()), r;
	if (c < d) swap(c, d);
	for (;;) {
		r = c % d;
		if (r == 0) break;
		c = d;
		d = r;
	};
	if (d.getSign() != a.getSign()) d = -d;
	return d;
}
 
BigInt BigMath::lcm(const BigInt& a, const BigInt& b) {
	return a * b / gcd(a, b);
}
 
BigInt BigMath::inverse(const BigInt& num, const BigInt& nrm) {
	BigInt a(num.abs()), b(nrm.abs()), r, q, c, d(1), e(0);
	if (a < b) {
		swap(a, b);
		swap(d, e);
	}
	for (;;) {
		q = a / b;
		r = a % b;
		if (r == 0) break;
		BigInt t = e * q;
		c = d - t;
		d = e;
		e = c;
		a = b;
		b = r;
	};
	if (c.getSign() != nrm.getSign()) c += nrm;
	return c;
}
 
class MColPtr : public Pool<PrimitiveExArray<unsigned long> >::Ptr {
public:
	MColPtr();
protected:
	static Pool<PrimitiveExArray<unsigned long> > pool;
};
 
class MTabPtr : public Pool<ClassObjectExArray<MColPtr> >::Ptr {
public:
	MTabPtr();
protected:
	static Pool<ClassObjectExArray<MColPtr> > pool;
};
 
BigInt::BigInt() : sign(0) {}
 
BigInt::BigInt(const int& num) {
	this->sign = num == 0 ? 0 : (num > 0 ? 1 : -1);
	this->fld->setLong(num < 0 ? -num : num);
}
 
BigInt::BigInt(const string& str, const unsigned int& base) {
	this->sign = 1;
	this->fld->setLong(0);
	BFPtr base_fld(base);
	auto iter = str.begin();
	if (*iter == '+') {
		this->sign = 1;
		iter++;
	}
	else if (*iter == '-') {
		this->sign = -1;
		iter++;
	}
	for (; iter != str.end(); iter++) {
		if (iter != str.begin()) {
			this->fld = multiply(this->fld, base_fld);
		}
		unsigned int num = digitToNumber(*iter);
		if (num >= base) throw string("値が範囲を逸脱している。");
		this->fld = add(this->fld, BFPtr(num));
	}
	if (this->fld->isZero()) this->sign = 0;
}
 
BigInt::BigInt(const int& sign, const BitField& fld) {
	this->sign = fld.isZero() ? 0 : sign;
	*this->fld = fld;
}
 
BigInt::BigInt(const BigInt& num) : sign(num.sign), fld(*num.fld) {}
 
BigInt BigInt::operator -() const {
	return BigInt(-this->sign, BFPtr(*this->fld));
}
 
BigInt BigInt::operator +(const BigInt& ade) const {
	BigInt res;
	if (this->sign == 0) 
		res = ade;
	else if (ade.sign == 0) 
		res = *this;
	else if (this->sign == ade.sign) 
		res = BigInt(this->sign, add(this->fld, ade.fld));
	else {
		int cmp_res = this->fld->compare(*ade.fld);
		if (cmp_res == 0) res.setInt(0);
		else {
			int sign;
			BFPtr gre_fld, less_fld;
			if (cmp_res > 0) {
				sign = this->sign;
				gre_fld = this->fld;
				less_fld = ade.fld;
			}
			else {
				sign = ade.sign;
				gre_fld = ade.fld;
				less_fld = this->fld;
			}
			res = BigInt(sign, subtract(gre_fld, less_fld));
		}
	}
	return res;
}
 
BigInt BigInt::operator -(const BigInt& sub) const {
	return operator +(-sub);
}
 
BigInt BigInt::operator *(const BigInt& mer) const {
	return BigInt(this->sign * mer.sign, multiply(this->fld, mer.fld));
}
 
BigInt BigInt::operator /(const BigInt& dsr) const {
	return BigInt(this->sign * dsr.sign, divide(this->fld, dsr.fld).first);
}
 
BigInt BigInt::operator %(const BigInt& nrm) const {
	return BigInt(this->sign, divide(this->fld, nrm.fld).second);
}
 
BigInt BigInt::operator <<(const unsigned int& num) const {
	BFPtr fld(*this->fld);
	fld->shift(-num);
	return BigInt(this->sign, fld);
}
 
BigInt BigInt::operator >>(const unsigned int& num) const {
	BFPtr fld(*this->fld);
	fld->shift(num);
	return BigInt(this->sign, fld);
}
 
BigInt& BigInt::operator =(const BigInt& num) {
	if (&num != this) {
		this->sign = num.sign;
		*this->fld = *num.fld;
	}
	return *this;
}
 
BigInt& BigInt::operator +=(const BigInt& add) {
	return *this = *this + add;
}
 
BigInt& BigInt::operator -=(const BigInt& sub) {
	return *this = *this - sub;
}
 
BigInt& BigInt::operator *=(const BigInt& mer) {
	return *this = *this * mer;
}
 
BigInt& BigInt::operator /=(const BigInt& dsr) {
	return *this = *this / dsr;
}
 
BigInt& BigInt::operator %=(const BigInt& nrm) {
	return *this = *this % nrm;
}
 
BigInt& BigInt::operator <<=(const size_t& num) {
	return *this = *this << num;
}
 
BigInt& BigInt::operator >>=(const size_t& num) {
	return *this = *this >> num;
}
 
BigInt& BigInt::operator ++() {
	return *this += 1;
}
 
BigInt BigInt::operator ++(int) {
	BigInt res = *this;
	*this += 1;
	return res;
}
 
BigInt& BigInt::operator --() {
	return *this -= 1;
}
 
BigInt BigInt::operator --(int) {
	BigInt res = *this;
	*this -= 1;
	return res;
}
 
bool BigInt::operator ==(const BigInt& num) const {
	if (&num == this) return true;
	return this->sign == num.sign && this->fld->compare(*num.fld) == 0;
}
 
bool BigInt::operator <(const BigInt& num) const {
	if (&num == this) return false;
	int cmp_res = this->fld->compare(*num.fld);
	return (this->sign >= 0 && num.sign >= 0 && cmp_res < 0) || 
		(this->sign < 0 && num.sign >= 0) || 
		(this->sign < 0 && num.sign < 0 && cmp_res > 0);
}
 
bool BigInt::operator >(const BigInt& num) const {
	if (&num == this) return false;
	int cmp_res = this->fld->compare(*num.fld);
	return (this->sign >= 0 && num.sign >= 0 && cmp_res > 0) || 
		(this->sign >= 0 && num.sign < 0) || 
		(this->sign < 0 && num.sign < 0 && cmp_res < 0);
}
 
bool BigInt::operator !=(const BigInt& num) const {
	return !operator ==(num);
}
 
bool BigInt::operator <=(const BigInt& num) const {
	return !operator >(num);
}
 
bool BigInt::operator >=(const BigInt& num) const {
	return !operator <(num);
}
 
BigInt BigInt::abs() const {
	return BigInt(1, BFPtr(*this->fld));
}
 
bool BigInt::isZero() const {
	return this->fld->isZero();
}
 
int BigInt::getSign() const {
	return this->sign;
}
 
bool BigInt::getLSBit() const {
	return this->fld->getLSBit();
}
 
unsigned long BigInt::getLSLong() const {
	return this->fld->getLSLong();
}
 
void BigInt::setInt(const int& num) {
	this->sign = num == 0 ? 0 : (num > 0 ? 1 : -1);
	this->fld->setLong(num < 0 ? -num : num);
}
 
string BigInt::toString(const unsigned int& base) const {
	string res = "";
	pair<BFPtr, BFPtr> quo_rem(BFPtr(*this->fld), BFPtr());
	BFPtr base_fld;
	base_fld->setLong(base);
	while (!quo_rem.first->isZero()) {
		quo_rem = divide(quo_rem.first, base_fld);
		res += numberToDigit(quo_rem.second->getLSLong());
	}
	if (res.empty()) res += '0';
	if (this->sign < 0) res += '-';
	reverse(res.begin(), res.end());
	size_t pos = 0;
	for (; pos < res.length() - 1; pos++) if (res[pos] != '0') break;
	return res.substr(pos, res.length() - pos);
}
 
unsigned int BigInt::getLength() const {
	return this->fld->getLength();
}
 
BigInt::BFPtr::BFPtr() : Pool<BitField>::Ptr(&pool) {
	this->x_cnt.first->clear();
}
 
BigInt::BFPtr::BFPtr(const unsigned long& num) : Pool<BitField>::Ptr(&pool) {
	this->x_cnt.first->setLong(num);
}
 
BigInt::BFPtr::BFPtr(const BitField& fld) : Pool<BitField>::Ptr(&pool) {
	*this->x_cnt.first = fld;
}
 
Pool<BitField> BigInt::BFPtr::pool;
 
BigInt::BigInt(const int& sign, const BFPtr& fld) {
	this->sign = fld->isZero() ? 0 : sign;
	this->fld = fld;
}
 
const unsigned int BigInt::LONG_LEN = sizeof(unsigned long) << 3;
 
BigInt::BFPtr BigInt::add(const BFPtr& age, const BFPtr& ade) {
	BFPtr sum;
	BitField::LongOutputStream sum_out(sum.get());
	BitField::LongInputStream age_in(age.get());
	BitField::LongInputStream ade_in(ade.get());
	bool carry = false;
	while (!age_in.isEOF() || !ade_in.isEOF()) {
		unsigned long age_num = !age_in.isEOF() ? age_in.getLong() : 0;
		unsigned long ade_num = !ade_in.isEOF() ? ade_in.getLong() : 0;
		unsigned long sum_num = (age_num & ((1 << (LONG_LEN - 1)) - 1)) + (ade_num & ((1 << (LONG_LEN - 1)) - 1)) + (carry ? 1 : 0);
		int ms_num = (age_num >> (LONG_LEN - 1)) + (ade_num >> (LONG_LEN - 1)) + (sum_num >> (LONG_LEN - 1));
		carry = ms_num > 1;
		if (carry) ms_num -= 2;
		sum_num = (sum_num & ((1 << (LONG_LEN - 1)) - 1)) | (ms_num << (LONG_LEN - 1));
		sum_out.putLong(sum_num);
	}
	sum_out.flush();
	if (carry) sum->pushMS(true);
	if (sum->isEmpty()) sum->pushMS(false);
	else sum->trim();
	return sum;
}
 
BigInt::BFPtr BigInt::subtract(const BFPtr& min, const BFPtr& sub) {
	BFPtr dif;
	BitField::LongOutputStream dif_out(dif.get());
	BitField::LongInputStream min_in(min.get());
	BitField::LongInputStream sub_in(sub.get());
	bool borrow = false;
	while (!min_in.isEOF() || !sub_in.isEOF()) {
		unsigned int min_num = !min_in.isEOF() ? min_in.getLong() : 0;
		unsigned int sub_num = !sub_in.isEOF() ? sub_in.getLong() : 0;
		unsigned int dif_num = (min_num | (1 << (LONG_LEN - 1))) - (sub_num & ((1 << (LONG_LEN - 1)) - 1)) - (borrow ? 1 : 0);
		int ms_num = (min_num >> (LONG_LEN - 1)) - (sub_num >> (LONG_LEN - 1)) - (1 - (dif_num >> (LONG_LEN - 1)));
		borrow = ms_num < 0;
		if (borrow) ms_num += 2;
		dif_num = (dif_num & ((1 << (LONG_LEN - 1)) - 1)) | (ms_num << (LONG_LEN - 1));
		dif_out.putLong(dif_num);
	}
	dif_out.flush();
	if (borrow) throw string("被減数が減数より小さい。");
	if (dif->isEmpty()) dif->pushMS(false);
	else dif->trim();
	return dif;
}
 
BigInt::BFPtr BigInt::multiply(const BFPtr& mca, const BFPtr& mer) {
	BFPtr pro;
	if (mca->isPowerOf2()) {
		*pro = *mer;
		pro->shift(-(mca->getLength() - 1));
	}
	else if (mer->isPowerOf2()) {
		*pro = *mca;
		pro->shift(-(mer->getLength() - 1));
	}
	else {
		BitField::LongOutputStream pro_out(pro.get());
		BitField::LongInputStream mer_in(mer.get());
		MTabPtr tab;
		for (unsigned int base_col = 0; !mer_in.isEOF(); base_col++) {
			unsigned long mer_num = mer_in.getLong();
			BitField::LongInputStream mca_in(mca.get());
			for (unsigned int col = base_col; !mca_in.isEOF(); col++) {
				unsigned long mca_num = mca_in.getLong();
				unsigned long long pro_num = (unsigned long long)mer_num * mca_num;
				unsigned long rem_num = pro_num & (((unsigned long long)1 << LONG_LEN) - 1);
				unsigned long carry_num = pro_num >> LONG_LEN;
				if (tab->getSize() <= col) tab->push(MColPtr());
				tab->at(col)->push(rem_num);
				if (carry_num != 0) {
					if (tab->getSize() <= col + 1) tab->push(MColPtr());
					tab->at(col + 1)->push(carry_num);
				}
			}
		}
		for (unsigned int col = 0; col < tab->getSize(); col++) {
			unsigned long age_num = 0;
			unsigned long carry_num = 0;
			for (unsigned int i = 0; i < tab->at(col)->getSize(); i++) {
				unsigned long ade_num = tab->at(col)->at(i);
				unsigned long sum_num = (age_num & ((1 << (LONG_LEN - 1)) - 1)) + (ade_num & ((1 << (LONG_LEN - 1)) - 1));
				int ms_num = (age_num >> (LONG_LEN - 1)) + (ade_num >> (LONG_LEN - 1)) + (sum_num >> (LONG_LEN - 1));
				if (ms_num > 1) {
					carry_num++;
					ms_num -= 2;
				}
				age_num = (sum_num & ((1 << (LONG_LEN - 1)) - 1)) | (ms_num << (LONG_LEN - 1));
			}
			pro_out.putLong(age_num);
			if (carry_num != 0) {
				if (tab->getSize() <= col + 1) tab->push(MColPtr());
				tab->at(col + 1)->push(carry_num);
			}
		}
		pro_out.flush();
	}
	if (pro->isEmpty()) pro->pushMS(false);
	else pro->trim();
	return pro;
}
 
pair<BigInt::BFPtr, BigInt::BFPtr> BigInt::divide(const BFPtr& dde, const BFPtr& dsr) {
	if (dsr->isZero()) throw string("除数がゼロ。");
	pair<BFPtr, BFPtr> quo_rem;
	int cmp_res = dde->compare(*dsr);
	if (cmp_res == 0) {
		quo_rem.first->setLong(1);
		quo_rem.second->setLong(0);
	}
	else if (cmp_res < 0) {
		quo_rem.first->setLong(0);
		*quo_rem.second = *dde;
	}
	else if (dsr->isPowerOf2()) {
		*quo_rem.first = *dde;
		quo_rem.first->shift(dsr->getLength() - 1);
		*quo_rem.second = dde->getSubfield(0, dsr->getLength() - 1);
	}
	else {
		BitField::ReverseLongOutputStream quo_out(quo_rem.first.get());
		unsigned int k = (32 - (dsr->getLength() & (32 - 1))) & (32 - 1);
		BFPtr k_dde(*dde);
		k_dde->shift(-k);
		BFPtr k_dsr(*dsr);
		k_dsr->shift(-k);
		BitField::ReverseLongInputStream dde_in(k_dde.get());
		BitField::ReverseLongInputStream dsr_in(k_dsr.get());
		unsigned long dsr_ms_num = dsr_in.getLong();
		while (!dde_in.isEOF()) {
			BitField::ReverseLongOutputStream rem_out(quo_rem.second.get());
			rem_out.putLong(dde_in.getLong());
			rem_out.flush();
			quo_rem.second->trim();
			int cmp_res = quo_rem.second->compare(*k_dsr);
			if (cmp_res == 0) {
				quo_out.putLong(1);
				quo_rem.second->clear();
			}
			else if (cmp_res < 0) quo_out.putLong(0);
			else {
				BitField::ReverseLongInputStream rem_in(quo_rem.second.get());
				unsigned long long rem_ms_num = rem_in.getLong();
				if (rem_ms_num < dsr_ms_num) 
					rem_ms_num = (rem_ms_num << 32) | rem_in.getLong();
				unsigned long long quo_num = rem_ms_num / dsr_ms_num;
				if (quo_num >= ((unsigned long long)1 << 32)) 
					quo_num = ((unsigned long long)1 << 32) - 1;
				BFPtr pro = multiply(k_dsr, BFPtr(quo_num));
				while (quo_rem.second->compare(*pro) < 0) {
					quo_num--;
					quo_rem.second = add(quo_rem.second, k_dsr);
				}
				quo_out.putLong(quo_num);
				quo_rem.second = subtract(quo_rem.second, pro);
			}
		}
		quo_out.flush();
		quo_rem.second->shift(k);
	}
	if (quo_rem.first->isEmpty()) quo_rem.first->pushMS(false);
	else quo_rem.first->trim();
	if (quo_rem.second->isEmpty()) quo_rem.second->pushMS(false);
	else quo_rem.second->trim();
	return quo_rem;
}
 
unsigned int BigInt::digitToNumber(const char& dig) {
	unsigned int res;
	if (dig >= '0' && dig <= '9') res = dig - '0';
	else if (dig >= 'A' && dig <= 'Z') res = 10 + dig - 'A';
	else if (dig >= 'a' && dig <= 'z') res = 10 + dig - 'a';
	else throw string("文字が数ではない。");
	return res;
}
 
char BigInt::numberToDigit(const unsigned int& num) {
	char res;
	if (num >= 0 && num <= 9) res = '0' + num;
	else if (num >= 10 && num <= 36) res = 'a' + (num - 10);
	else throw string("数が範囲を逸脱している。");
	return res;
}
 
MColPtr::MColPtr() : Pool<PrimitiveExArray<unsigned long> >::Ptr(&pool) {
	this->x_cnt.first->clear();
}
 
Pool<PrimitiveExArray<unsigned long> > MColPtr::pool;
 
MTabPtr::MTabPtr() : Pool<ClassObjectExArray<MColPtr> >::Ptr(&pool) {
	this->x_cnt.first->clear();
}
 
Pool<ClassObjectExArray<MColPtr> > MTabPtr::pool;
 
BitField::LongInputStream::LongInputStream(const BitField* fld) {
	this->fld = fld;
	this->rem = this->fld->len;
	if (this->rem != 0) {
		this->high_len = this->fld->beg & (32 - 1);
		this->low_len = 32 - this->high_len;
		this->high_mask = (1 << this->high_len) - 1;
		this->low_mask = ~this->high_mask;
		this->end = this->fld->buf_sz >> 2;
		this->cur = this->fld->beg >> 5;
		this->num = ((unsigned long*)this->fld->buf)[this->cur];
	}
}
 
bool BitField::LongInputStream::isEOF() const {
	return this->rem == 0;
}
 
unsigned long BitField::LongInputStream::getLong() {
	unsigned int res = 0;
	res |= (this->num & this->low_mask) >> this->high_len;
	if (this->rem >= this->low_len) {
		this->rem -= this->low_len;
		if (this->rem != 0) {
			this->cur++;
			if (this->cur == this->end) this->cur = 0;
			this->num = ((unsigned long*)this->fld->buf)[this->cur];
			if (this->high_len != 0) {
				res |= (this->num & this->high_mask) << this->low_len;
				if (this->rem >= this->high_len) 
					this->rem -= this->high_len;
				else {
					res &= (1 << (this->low_len + this->rem)) - 1;
					this->rem = 0;
				}
			}
		}
	}
	else {
		res &= (1 << this->rem) - 1;
		this->rem = 0;
	}
	return res;
}
 
BitField::LongOutputStream::LongOutputStream(BitField* fld) {
	this->fld = fld;
	unsigned int fld_end = this->fld->beg + this->fld->len;
	unsigned int buf_len = this->fld->buf_sz << 3;
	unsigned int act_fld_end;
	if (fld_end <= buf_len) act_fld_end = fld_end;
	else act_fld_end = fld_end - buf_len;
	this->high_len = act_fld_end & (32 - 1);
	this->low_len = 32 - this->high_len;
	this->high_mask = (1 << this->high_len) - 1;
	this->low_mask = ~this->high_mask;
	this->cur = act_fld_end >> 5;
	unsigned int end = this->fld->buf_sz >> 2;
	if (this->fld->len != 0 && this->cur != end) 
		this->high_buf = ((unsigned long*)this->fld->buf)[this->cur] & this->high_mask;
	else this->high_buf = 0;
	this->bufed = false;
}
 
BitField::LongOutputStream::~LongOutputStream() {
	flush();
}
 
void BitField::LongOutputStream::putLong(const unsigned long& num) {
	this->fld->extendIfNecessary(32);
	unsigned int end = this->fld->buf_sz >> 2;
	if (this->cur == end) this->cur = 0;
	((unsigned long*)this->fld->buf)[this->cur] = this->high_buf | (num << this->high_len);
	if (this->high_len != 0) {
		this->high_buf = num >> this->low_len;
		this->bufed = true;
	}
	this->cur++;
}
 
void BitField::LongOutputStream::flush() {
	if (this->bufed) {
		unsigned int fld_end = this->fld->beg + this->fld->len;
		unsigned int buf_len = this->fld->buf_sz << 3;
		unsigned int act_fld_end;
		if (fld_end <= buf_len) act_fld_end = fld_end;
		else act_fld_end = fld_end - buf_len;
		unsigned int cur = act_fld_end >> 5;
		if (cur == 0) cur = (this->fld->buf_sz >> 2) - 1;
		else cur--;
		((unsigned long*)this->fld->buf)[cur] = 
			this->high_buf | (((unsigned long*)this->fld->buf)[cur] & this->low_mask);
		this->bufed = false;
	}
}
 
BitField::ReverseLongInputStream::ReverseLongInputStream(const BitField* fld) {
	this->fld = fld;
	this->rem = this->fld->len;
	if (this->rem != 0) {
		this->end = this->fld->buf_sz >> 2;
		this->high_len = this->fld->beg & (32 - 1);
		this->low_len = 32 - this->high_len;
		this->high_mask = (1 << this->high_len) - 1;
		this->low_mask = ~this->high_mask;
		unsigned int fld_end = this->fld->beg + this->fld->len;
		unsigned int buf_len = this->fld->buf_sz << 3;
		unsigned int act_fld_end;
		if (fld_end <= buf_len) act_fld_end = fld_end;
		else act_fld_end = fld_end - buf_len;
		unsigned int last_len = act_fld_end & (32 - 1);
		if (last_len <= this->high_len) this->cur = act_fld_end >> 5;
		else this->cur = (act_fld_end + (32 - 1)) >> 5;
		if (this->cur != this->end) 
			this->num = ((unsigned long*)this->fld->buf)[this->cur];
	}
}
 
bool BitField::ReverseLongInputStream::isEOF() const {
	return this->rem == 0;
}
 
unsigned long BitField::ReverseLongInputStream::getLong() {
	unsigned int res = 0;
	unsigned int len = this->rem & (32 - 1);
	if (len == 0) len = 32;
	if (len > this->low_len) {
		res |= this->num & this->high_mask;
		unsigned int high_len = len - this->low_len;
		if (high_len < this->high_len) 
			res &= (1 << high_len) - 1;
		res <<= this->low_len;
	}
	if (this->cur == 0) this->cur = this->end;
	this->cur--;
	this->num = ((unsigned long*)this->fld->buf)[this->cur];
	res |= (this->num & this->low_mask) >> this->high_len;
	if (len < this->low_len) res &= (1 << len) - 1;
	this->rem -= len;
	return res;
}
 
BitField::ReverseLongOutputStream::ReverseLongOutputStream(BitField* fld) {
	this->fld = fld;
	this->high_len = this->fld->beg & (32 - 1);
	this->low_len = 32 - this->high_len;
	this->high_mask = (1 << this->high_len) - 1;
	this->low_mask = ~this->high_mask;
	unsigned int cur = this->fld->beg >> 5;
	unsigned int end = this->fld->buf_sz >> 2;
	if (this->fld->len != 0 && cur != end) 
		this->low_buf = ((unsigned long*)this->fld->buf)[cur] & this->low_mask;
	else this->low_buf = 0;
	this->bufed = false;
}
 
BitField::ReverseLongOutputStream::~ReverseLongOutputStream() {
	flush();
}
 
void BitField::ReverseLongOutputStream::putLong(const unsigned long& num) {
	this->fld->extendIfNecessary(-32);
	unsigned int cur = (this->fld->beg >> 5) + 1;
	unsigned int end = this->fld->buf_sz >> 2;
	if (cur == end) cur = 0;
	if (this->high_len != 0) {
		((unsigned long*)this->fld->buf)[cur] = (num >> this->low_len) | this->low_buf;
		this->low_buf = num << this->high_len;
	}
	else {
		((unsigned long*)this->fld->buf)[cur] = this->low_buf;
		this->low_buf = num;
	}
	this->bufed = true;
}
 
void BitField::ReverseLongOutputStream::flush() {
	if (this->bufed) {
		unsigned int cur = this->fld->beg >> 5;
		((unsigned long*)this->fld->buf)[cur] = 
			(((unsigned long*)this->fld->buf)[cur] & this->high_mask) | this->low_buf;
		this->bufed = false;
	}
}
 
BitField::BitField() : buf(nullptr), buf_sz(0), beg(0), len(0) {}
 
BitField::BitField(const unsigned long& num) : buf(nullptr), buf_sz(0), beg(0), len(0) {
	extendIfNecessary(32);
	*(unsigned long*)this->buf = num;
	trim();
}
 
BitField::BitField(const BitField& fld) : buf(nullptr), buf_sz(0), beg(0), len(0) {
	if (fld.len != 0) {
		this->buf_sz = fld.buf_sz;
		this->buf = new unsigned char[this->buf_sz];
		memcpy(this->buf, fld.buf, fld.buf_sz);
		this->beg = fld.beg;
		this->len = fld.len;
	}
}
 
BitField::~BitField() {
	if (this->buf) delete[] this->buf;
}
 
BitField& BitField::operator =(const BitField& fld) {
	if (&fld != this) {
		this->len = 0;
		if (fld.len != 0) {
			this->buf_sz = fld.buf_sz;
			this->buf = new unsigned char[this->buf_sz];
			memcpy(this->buf, fld.buf, fld.buf_sz);
			this->beg = fld.beg;
			this->len = fld.len;
		}
	}
	return *this;
}
 
unsigned int BitField::getLength() const {
	return this->len;
}
 
bool BitField::isEmpty() const {
	return this->len == 0;
}
 
bool BitField::isZero() const {
	bool res = true;
	for (unsigned int pos = 0; pos < this->len; pos++) {
		if (getBit(pos) == true) {
			res = false;
			break;
		}
	}
	return res;
}
 
bool BitField::getBit(const unsigned int& pos) const {
	unsigned int abs_pos = this->beg + pos;
	unsigned int buf_len = this->buf_sz << 3;
	if (abs_pos >= buf_len) abs_pos -= buf_len;
	return ((this->buf[abs_pos >> 3] >> (abs_pos & (8 - 1))) & 1) == 1;
}
 
bool BitField::getLSBit() const {
	return getBit(0);
}
 
bool BitField::getMSBit() const {
	return getBit(this->len - 1);
}
 
unsigned long BitField::getLong(const unsigned int& ls_pos) const {
	unsigned long res = 0;
	for (unsigned int pos = 0; pos < 32 && ls_pos + pos < this->len; pos++) 
		res |= (getBit(ls_pos + pos) == true ? 1 : 0) << pos;
	return res;
}
 
unsigned long BitField::getLSLong() const {
	unsigned long res = 0;
	for (unsigned int pos = 0; pos < 32 && pos < this->len; pos++) 
		res |= (getBit(pos) == true ? 1 : 0) << pos;
	return res;
}
 
void BitField::setBit(const unsigned int& pos, const bool& bit) {
	unsigned int abs_pos = this->beg + pos;
	unsigned int buf_len = this->buf_sz << 3;
	if (abs_pos >= buf_len) abs_pos -= buf_len;
	if (bit) this->buf[abs_pos >> 3] |= 1 << (abs_pos & (8 - 1));
	else this->buf[abs_pos >> 3] &= ~(1 << (abs_pos & (8 - 1)));
}
 
void BitField::pushMS(const bool& bit) {
	extendIfNecessary(1);
	setBit(this->len - 1, bit);
}
 
template <class X> void BitField::pushMS(const X& x) {
	for (unsigned int pos = 0; pos < (sizeof(X) << 3); pos++) 
		pushMS(((x >> pos) & 1) == 1);
}
 
void BitField::pushLS(const bool& bit) {
	extendIfNecessary(-1);
	setBit(0, bit);
}
 
template <class X> void BitField::pushLS(const X& x) {
	for (unsigned int pos = 0; pos < (sizeof(X) << 3); pos++) 
		pushLS(((x >> ((sizeof(X) << 3) - 1 - pos)) & 1) == 1);
}
 
void BitField::setLong(const unsigned long& num) {
	clear();
	extendIfNecessary(32);
	*(unsigned int*)this->buf = num;
	trim();
}
 
void BitField::shift(const int& num) {
	if (num < 0) {
		extendIfNecessary(num);
		for (unsigned int pos = 0; pos < -num; pos++) 
			setBit(pos, false);
	}
	else if (num > 0) {
		unsigned int act_num;
		if (num <= this->len) act_num = num;
		else act_num = this->len;
		this->beg += act_num;
		unsigned int buf_len = this->buf_sz << 3;
		if (this->beg >= buf_len) this->beg -= buf_len;
		this->len -= act_num;
	}
}
 
void BitField::trim() {
	while (this->len > 1 && getMSBit() == false) this->len--;
}
 
void BitField::clear() {
	this->beg = 0;
	this->len = 0;
}
 
int BitField::compare(const BitField& fld) const {
	int res = 0;
	if (&fld != this) {
		for (unsigned int next_pos = this->len < fld.len ? fld.len : this->len; next_pos > 0; next_pos--) {
			unsigned int pos = next_pos - 1;
			bool bit1 = pos < this->len ? getBit(pos) : false;
			bool bit2 = pos < fld.len ? fld.getBit(pos) : false;
			if (bit1 == false && bit2 == true) {
				res = -1;
				break;
			}
			else if (bit1 == true && bit2 == false) {
				res = 1;
				break;
			}
		}
	}
	return res;
}
 
string BitField::toString() const {
	string res = "";
	for (unsigned int pos = 0; pos < this->len; pos++) 
		res += getBit(pos) == true ? '1' : '0';
	return res;
}
 
bool BitField::isPowerOf2() const {
	unsigned int cnt = 0;
	for (unsigned int pos = 0; pos < this->len; pos++) {
		if (getBit(pos) == true) {
			cnt++;
			if (cnt > 1) break;
		}
	}
	return cnt == 1;
}
 
BitField BitField::getSubfield(const unsigned int& ls_pos, const unsigned int& len) const {
	BitField res;
	for (unsigned int pos = 0; pos < len; pos++) 
		res.pushMS(getBit(ls_pos + pos));
	return res;
}
 
void BitField::extendIfNecessary(const int& len) {
	unsigned int abs_len = len < 0 ? -len : len;
	unsigned int need_sz = ((((this->len + abs_len + (8 - 1)) >> 3) + (4 - 1)) >> 2) << 2;
	if (need_sz > this->buf_sz) {
		unsigned int new_buf_sz = need_sz << 1;
		unsigned char* new_buf = new unsigned char[new_buf_sz];
		unsigned int new_beg = 0;
		if (this->len != 0) {
			unsigned int fld_beg = this->beg >> 3;
			unsigned int fld_end = (this->beg + this->len + (8 - 1)) >> 3;
			if (fld_end <= this->buf_sz) {
				unsigned int fld_sz = fld_end - fld_beg;
				memcpy(new_buf + fld_beg, this->buf + fld_beg, fld_sz);
				new_beg = this->beg;
			}
			else {
				unsigned int low_sz = this->buf_sz - fld_beg;
				unsigned int new_low_beg = new_buf_sz - low_sz;
				memcpy(new_buf + new_low_beg, this->buf + fld_beg, low_sz);
				unsigned int high_sz = fld_end - this->buf_sz;
				memcpy(new_buf, this->buf, high_sz);
				unsigned int buf_len = this->buf_sz << 3;
				unsigned int low_len = buf_len - this->beg;
				unsigned int new_buf_len = new_buf_sz << 3;
				new_beg = new_buf_len - low_len;
			}
			delete[] this->buf;
		}
		this->buf_sz = new_buf_sz;
		this->buf = new_buf;
		this->beg = new_beg;
	}
	if (len < 0) {
		this->beg += len;
		int buf_len = this->buf_sz << 3;
		if (this->beg < 0) this->beg += buf_len;
	}
	this->len += abs_len;
}
 
template <class X> 
PrimitiveBitInputStream<X>::PrimitiveBitInputStream(const X& x) : x(x), pos(0) {}
 
template <class X> 
bool PrimitiveBitInputStream<X>::getBit() {
	bool res = ((this->x >> ((sizeof(X) << 3) - 1 - this->pos)) & 1) == 1;
	this->pos++;
	return res;
}
 
template <class X> 
bool PrimitiveBitInputStream<X>::isEOF() {
	return this->pos >= (sizeof(X) << 3);
}
 
template <class X> 
Pool<X>::Ptr::Ptr(Pool* pool) : pool(pool) {
	this->x_cnt = this->pool->get();
	if (this->x_cnt.second) (*this->x_cnt.second)++;
}
 
template <class X> 
Pool<X>::Ptr::Ptr(const Ptr& ptr) {
	this->pool = ptr.pool;
	this->x_cnt = ptr.x_cnt;
	if (this->x_cnt.second) (*this->x_cnt.second)++;
}
 
template <class X> 
Pool<X>::Ptr::~Ptr() {
	release();
}
 
template <class X> 
typename Pool<X>::Ptr& Pool<X>::Ptr::operator =(const Ptr& ptr) {
	if (&ptr != this) {
		release();
		this->x_cnt = ptr.x_cnt;
		if (this->x_cnt.second) (*this->x_cnt.second)++;
	}
	return *this;
}
 
template <class X> 
X& Pool<X>::Ptr::operator *() const {
	return *this->x_cnt.first;
}
 
template <class X> 
X* Pool<X>::Ptr::operator ->() const {
	return this->x_cnt.first;
}
 
template <class X> 
X* Pool<X>::Ptr::get() const {
	return this->x_cnt.first;
}
 
template <class X> 
void Pool<X>::Ptr::release() {
	if (this->x_cnt.second) {
		(*this->x_cnt.second)--;
		if (*this->x_cnt.second == 0) 
		pool->putBack(this->x_cnt);
	}
}
 
template <class X> 
Pool<X>::~Pool() {
	for (unsigned int i = 0; i < this->xa.getSize(); i++) {
		delete this->xa.at(i).first;
		delete this->xa.at(i).second;
	}
}
 
template <class X> 
pair<X*, unsigned int*> Pool<X>::get() {
	if (this->xa.isEmpty()) this->xa.push(make_pair(new X, new unsigned int(0)));
	pair<X*, unsigned int*> res = this->xa.last();
	this->xa.pop();
	return res;
}
 
template <class X> 
void Pool<X>::putBack(const pair<X*, unsigned int*>& x_cnt) {
	this->xa.push(x_cnt);
}
 
template <class X> 
PrimitiveExArray<X>::PrimitiveExArray(const unsigned int& sz) : buf(nullptr), buf_sz(0), sz(0) {
	resize(sz);
}
 
template <class X> 
PrimitiveExArray<X>::PrimitiveExArray(const PrimitiveExArray& a) : buf(nullptr), buf_sz(0), sz(0) {
	if (a.sz != 0) {
		if (this->buf) delete[] this->buf;
		this->buf_sz = a.buf_sz;
		this->buf = new X[this->buf_sz];
		this->sz = a.sz;
		memcpy(this->buf, a.buf, sizeof(X) * this->sz);
	}
}
 
template <class X> 
PrimitiveExArray<X>::~PrimitiveExArray() {
	if (this->buf) delete[] this->buf;
}
 
template <class X> 
PrimitiveExArray<X>& PrimitiveExArray<X>::operator =(const PrimitiveExArray& a) {
	if (&a != this && a.sz != 0) {
		if (this->buf) delete[] this->buf;
		this->buf_sz = a.buf_sz;
		this->buf = new X[this->buf_sz];
		this->sz = a.sz;
		memcpy(this->buf, a.buf, sizeof(X) * this->sz);
	}
	return *this;
}
 
template <class X> 
X& PrimitiveExArray<X>::operator [](const unsigned int& i) {
	return this->buf[i];
}
 
template <class X> 
X& PrimitiveExArray<X>::at(const unsigned int& i) {
	return this->buf[i];
}
 
template <class X> 
X& PrimitiveExArray<X>::last() {
	return this->buf[this->sz - 1];
}
 
template <class X> 
unsigned int PrimitiveExArray<X>::getSize() const {
	return this->sz;
}
 
template <class X> 
bool PrimitiveExArray<X>::isEmpty() const {
	return this->sz == 0;
}
 
template <class X> 
void PrimitiveExArray<X>::push(const X& x) {
	resize(this->sz + 1);
	this->buf[this->sz - 1] = x;
}
 
template <class X> 
void PrimitiveExArray<X>::pop() {
	this->sz--;
}
 
template <class X> 
void PrimitiveExArray<X>::clear() {
	this->sz = 0;
}
 
template <class X> 
void PrimitiveExArray<X>::resize(const unsigned int& sz) {
	if (sz > this->buf_sz) {
		unsigned int new_buf_sz = sz << 1;
		X* new_buf = new X[new_buf_sz];
		if (this->buf_sz != 0) {
			memcpy(new_buf, this->buf, sizeof(X) * this->sz);
			delete[] this->buf;
		}
		this->buf = new_buf;
		this->buf_sz = new_buf_sz;
	}
	this->sz = sz;
}
 
template <class X> 
ClassObjectExArray<X>::ClassObjectExArray(const unsigned int& sz) : buf(nullptr), buf_sz(0), sz(0) {
	resize(sz);
}
 
template <class X> 
ClassObjectExArray<X>::ClassObjectExArray(const ClassObjectExArray& a) : buf(nullptr), buf_sz(0), sz(0) {
	if (a.sz != 0) {
		if (this->buf) delete[] this->buf;
		this->buf_sz = a.buf_sz;
		this->buf = new X[this->buf_sz];
		this->sz = a.sz;
		copy(a.buf, a.buf + a.sz, this->buf);
	}
}
 
template <class X> 
ClassObjectExArray<X>& ClassObjectExArray<X>::operator =(const ClassObjectExArray& a) {
	if (&a != this && a.sz != 0) {
		if (this->buf) delete[] this->buf;
		this->buf_sz = a.buf_sz;
		this->buf = new X[this->buf_sz];
		this->sz = a.sz;
		copy(a.buf, a.buf + a.sz, this->buf);
	}
	return *this;
}
 
template <class X> 
ClassObjectExArray<X>::~ClassObjectExArray() {
	if (this->buf) delete[] this->buf;
}
 
template <class X> 
X& ClassObjectExArray<X>::operator [](const unsigned int& i) {
	return this->buf[i];
}
 
template <class X> 
X& ClassObjectExArray<X>::at(const unsigned int& i) {
	return this->buf[i];
}
 
template <class X> 
X& ClassObjectExArray<X>::last() {
	return this->buf[this->sz - 1];
}
 
template <class X> 
unsigned int ClassObjectExArray<X>::getSize() const {
	return this->sz;
}
 
template <class X> 
bool ClassObjectExArray<X>::isEmpty() const {
	return this->sz == 0;
}
 
template <class X> 
void ClassObjectExArray<X>::push(const X& x) {
	resize(this->sz + 1);
	this->buf[this->sz - 1] = x;
}
 
template <class X> 
void ClassObjectExArray<X>::pop() {
	this->buf[this->sz - 1] = X();
	this->sz--;
}
 
template <class X> 
void ClassObjectExArray<X>::clear() {
	for (unsigned int i = 0; i < this->sz; i++) this->buf[i] = X();
	this->sz = 0;
}
 
template <class X> 
void ClassObjectExArray<X>::resize(const unsigned int& sz) {
	if (sz > this->buf_sz) {
		unsigned int new_buf_sz = sz << 1;
		X* new_buf = new X[new_buf_sz];
		if (this->buf_sz != 0) {
			copy(this->buf, this->buf + this->sz, new_buf);
			delete[] this->buf;
		}
		this->buf = new_buf;
		this->buf_sz = new_buf_sz;
	}
	else if (sz < this->sz) for (unsigned int i = sz; i < this->sz; i++) this->buf[i] = X();
	this->sz = sz;
}
 
template <class X> X  rotateLeft(const X& x, const unsigned int& n, const unsigned int& w) {
	return (x << n) | (x >> (w - n));
}
 
int main() {
	try {
		clock_t begin = clock();
 
		shared_ptr<RPG> rpg(new SimpleRPG());
		cout << rpg->generatePrime(256).toString() << endl;
 
		clock_t end = clock();
		clock_t elapsed = end - begin;
		cout << (elapsed / CLOCKS_PER_SEC) << "." << setfill('0') << setw(3) << ((elapsed % CLOCKS_PER_SEC) * 1000 / CLOCKS_PER_SEC) << " secs" << endl;
	}
	catch (const string& msg) {
		cerr << msg << endl;
		return 1;
	}
	return 0;
}