Из принципа пришлось решить задачу, прошла, даже - просвистела на второе место :) очень быстро.
Мы точно можем оценить максимальный размер числа, так что знаем, какой массив данных нам понадобится. Я пошел по пути N*N
удвоений, с последующим вычитанием 1. Нам нужны только две операции - удвоение и вычитание 1. Берем массив в 350 (с запасом) unsigned long
, и N*N
раз удваиваем (суммируем соответствующие элементы, выполняем, если надо, перенос). Чтоб быстрей потом преобразовывать в десятичное - в каждом элементе массива значения ограничены одним миллиардом. Отслеживаю размер числа - чтоб не суммировать лишнее...
Я, конечно, могу привести тут код, но не уверен, насколько это хорошо в смысле педагогическом :) Чуть-чуть покажу все же.
class bigNum
{
public:
bigNum() { a[0] = 1; }
void mul2();
void dec() { a[0]--; }
void out();
private:
static const int size = 350;
static const int lim = 1000000000;
unsigned long a[size] = { 0 };
int last = 1;
};
void bigNum::mul2()
{
unsigned long carry = 0;
for(int i = 0; i < last; ++i)
{
a[i] *= 2;
a[i] += carry;
if (a[i] >= lim)
{
carry = a[i]/lim;
a[i] %= lim;
}
else carry = 0;
}
if (carry)
{
a[last++] = carry;
}
};
P.S. Для подъема скорости можно множить, скажем, на 16 или там 64, соответствующим образом меняя размеры...