POJ 2109 Power of Cryptography

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
 
using namespace std;
 
const int bitlen = sizeof(long);
const int bitmax = 10000;
 
#define maxof(a,b) (a > b ? a : b)
 
int a;
string b;
 
/* Class Number
 * Represents a big number.
 */
template<int T>
class number {
	public:
		/* init a new number by a input of integer. */
		number(const long i) {
			init();
			if (i < bitmax) {
				bit[0] = 1;
				bit[T] = i;
				return;
			}
			long l = 0, j = i, m;
			while ((m = j / bitmax, j) != 0) {
				bit[T - l++] = j - m * bitmax;
				j = m;
			}
			bit[0] = l;
		}
		/* the real size of bit[] */
		long size() const {
			return bit[0];
		}
		void show() const {
			if (bit[0] == 0) {
				cout << "0";
				return;
			}
			for (int i = 0; i < bit[0]; ++i) {
				cout << bit[T - bit[0] + i + 1];
			}
			cout << "(" << bit[0] << ")" << endl;
		}
		string showToString() const {
			if (bit[0] == 0) {
				return string("0");
			}
			string s;
			char ct[5];
			for (int i = 0; i < bit[0]; ++i) {
				sprintf(ct, "%d", bit[T - bit[0] + i + 1]);
				int p = 4 - strlen(ct);
				if (p > 0 && i != 0)
					for (int f = 0; f < p; ++f)
						s.append ("0");
				s.append(ct);
			}
			return s;
		}
		number<T> operator+(const number<T> &num2) const {
			if (num2.size() == 0) {
				return *this;
			}
			int len = maxof(this->size(), num2.size()), jw = 0;
			number<T> sum(0);
			for (int a = 0; a < len; ++a) {
				sum.bit[T - a] = this->bit[T - a] + num2.bit[T - a] + jw;
				jw = 0;
				if (sum.bit[T - a] >= bitmax) {
					sum.bit[T - a] %= bitmax;
					jw = 1;
				}
			}
			if (jw == 1)
				len++;
			sum.bit[0] = len;
			return sum;
		}
		number<T> operator<<(const int i) const {
			if (i != 1)
				throw exception();
			number<T> tmp(*this);
			for (int i = tmp.size (); i > 0; --i)
				tmp.bit[T - i] = tmp.bit[T - i + 1];
			tmp.bit[T] = 0;
			tmp.bit[0]++;
			return tmp;
		}
		number<T> operator*(const number<T> &num2) const {
			if (this->size() == 0 || num2.size() == 0) {
				return number<T>(0); // 0
			}
			if (this->size() == 1 && num2.size() == 1) {
				return number<T>(this->bit[T] * num2.bit[T]);
			}
			number<T> sum(0);
			for (int a = 0; a < this->size(); ++a) {
				for (int b = 0; b < num2.size(); ++b) {
					int cj = this->bit[T - a] * num2.bit[T - b];
					number<T> tmp(cj);
					for (int c = 0; c < a + b; ++c) {
						tmp = tmp << 1;
					}
					sum = sum + tmp;
				}
			}
			return sum;
		}
		long bit[T + 1];
	private:
		void init()	{
			memset(bit, 0, sizeof(bit));
		}
};
 
typedef number<100> bignum;
 
bignum power(int i, int p) {
	bignum tmp(i), tmp2(i);
	for (int i = 0; i < p - 1; ++i)
		tmp = tmp * tmp2;
	return tmp;
}
 
void check(int l, int r) {
	if (l == r)	{
		cout << l << endl;
		return;
	}
	int m = (l + r) / 2;
	bignum tmp = power(m, a);
	string ss = tmp.showToString();
	if (b == ss) {
		cout << m << endl;
		return;
	}
	else {
		if (ss.size() > b.size() || (ss.size() == b.size() && ss > b)) {
			check (l, m - 1);
		}
		else {
			check (m + 1, r);
		}
	}
}
 
int main () {
	while (cin >> a >> b) {
		check(1, 1000000000);
	}
	return 0;
}