Задача g6_1021: 2^n

Вывести в файл output.txt число 2^n, n<=10000, n - натуральное. Входной файл input.txt в единственной строке содержит число n

Решение g6_1021:
Наконец-то мы дошли до длинной арифметики! 2^10000 имеет порядка 3000 десятичных знаков, так что ни о каких extended'ах, а тем более longint'ах речи быть не может.
Существует такое понятие - длинная арифметика - выполнение арифметических операций в массиве (естественно, с потерями в скорости, но что же делать). В нашем случае нам нужно реализовать одно из простейших действий над длинными числами - умножение на 2.
Для надежности заведем массив длиной 4000, состоящий из элементов типа byte. Их будет достаточно для хранения одной десятичной цифры(можно хранить 2 и даже чуть больше десятичных цифр, но это сопряжено с извращениями и усложнениями, так что не будем экономить память, а будем экономить время и нервы). Обнулим массив и присвоим 4000 элементу значение 1 = 2^0. Затем в цикле от 1 до n будем запускать процедуру умножения на 2.
Вы наверняка хорошо представляете процедуру умножения на 2 в столбик. Здесь все точно также! Двигаясь от последнего элемента к первому(он будет определяться динамически и в начальный момент времени равен 4000), мы будем умножать его на 2 и, в случае если он превысил 9, будем брать остаток от деления на 10, а результат деления заносить в специальную переменную - так называемый флаг переноса. Это можно ассоциировать с умножением в столбик, например 8*2 - 6 пишем, 1 в уме. Главное, не забыть прибавить значение счетчика к следующему разряду.
Если цикл закончился, а флаг переноса не равен 0, то следует уменьшить счетчик, указывающий на первую цифру числа(сначала он был равен 4000), и присвоить элементу с номером счетчика значение флага переноса. В принципе, можно было проходить весь массив от конца к началу, но многократное бесполезное умножение 2 на 0 заметно снижает скорость, что немаловажно.
Стоит заметить, что некоторые предпочитают записывать младшие разряды числа в начале массива, но это непринципиально ни по размеру памяти, ни по времени работы. Кому как удобнее.
Скачать тесты к задаче