Бинарное возведение в степень для больших значений работает следующим образом: 3

1. Для чётного числа n можно свести задачу к вдвое меньшей степени, потратив всего одну операцию умножения. 35 Для этого используется тождество: a^n = (a^{n/2})^2 = a^{n/2} * a^{n/2}. 3
2. Если степень n нечётна, то нужно перейти к степени n-1, которая будет уже чётной: a^n = a^{n-1} * a. 35

Таким образом, от степени n переходят: если она чётна, к n/2, а иначе — к n-1. 3 Всего будет не более 2 log n переходов, прежде чем придём к n = 0 (базе рекуррентной формулы). 3

Для больших чисел можно использовать массив, в который запихнуть длинное число и умножать его столбиком. 4