Say we wanted to calculate ana^n, one way we could do this is to iterate from 11 to nn, multiplying the value of aa on every iteration:

long long pow(int a, int n) {
    long long res = 1;
    for (int i = 0; i < n; ++i) {
        res *= a;
    }
    return res;
}

This is a naive approach, and the problem with it is that it's not practical for large aa or nn.

Binary exponentiation

Binary exponentiation is a trick which allows to calculate ana^n in logarithmic time (instead of linearly as required by the naive approach above).

If you know how this works, just skip this part.

The idea of binary exponentiation is, that we split the work using the binary representation of the exponent.

a=2,n=13a = 2, n = 13

Say we wanted to calculate ana^n

2132^{13} == 2110122^{1101_2} == 282 ^ 8 242 ^ 4 212 ^ 1

Since the number nn has exactly log⌊log2_2 nn+1+1 digits in base 22, we only need to perform O(log2log_2 n⁡n) multiplications, if we know the powers a1a^1, a2a^2, a4a^4, a8a^8, , alog2na^{⌊log_2n⌋}

So we only need to know a fast way to compute those. This is very easy, since an element in the sequence is just the square of the previous element.

21=22^1 = 2

22=(21)2=22=42^2 = (2^1)^2 = 2^2 = 4

24=(22)2=42=162^4 = (2^2)^2 = 4^2 = 16

28=(24)2=162=2562^8 = (2^4)^2 = 16^2 = 256

So to get the final answer for 2132^{13}, we only need to multiply three of them (skipping 222^2 because the corresponding bit in n is not set 1101):

213=256162=81922^{13} = 256⋅16⋅2 = 8192

The final complexity of this algorithm is O(log2n)O(log_2n): we have to compute log2nlog⁡_2n powers of aa, and then have to do at most log2nlog_2n multiplications to get the final answer from them.

Implementation

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

Go here Binary Exponentiation, to learn more about this technique.

Ternary exponentiation


Instead of using the binary representation of the exponent to split the work, we use the ternary representation

a=2,n=7a = 2, n = 7


The ternary representation of nn is 21321_3, which is (2×31+1×302\times3^1 + 1 \times 3^0)

27=22132 ^ 7 = 2^{21_3} == 22312 ^ {2 ⋅ 3^1} 21302 ^ {1⋅3^0} == 262^6 212^1

It may seem that we would be performing just log3nlog_3n multiplications, but thats not the case.
Take the above case for example,

27=26212^7 = 2^6 ⋅ 2^1
66 isn't a power of 33 (∄nN,3n=6\not\exists n \in N, 3^n = 6)

And the essence of the trick is that if we know the powers a1a^1, a3a^3, a9a^9, , alog3na^{⌊log_3n⌋}, we only need to perform O(log3log_3 n⁡n) multiplications. So what do we do.

The reason why in the binary exponentiation, the sum of the exponent can be represented as a sum of powers of 2 is because 'n%2{0,1}n\% 2 \in \{0,1\}',
or in words,
the digits in a binary number is either 00 or 11, so when converting back to decimal we multiply a power of 2 by 00 or by 11, multiplying by 11 doesn't change the result (it still remains a power of 2).

While in the ternary numbering system, 'n%3{0,1,2}n\%3 \in \{0,1,2\}', if we multiply a power of 33 by 22 , it's no longer a power of 3, but the result can be represented as a sum of powers of 33.

26=23+32^6 = 2^{3+3}

Which is also the same as (23)2(2^3)^2, so

27=2323212^7 = 2^3 ⋅ 2 ^ 3 ⋅ 2 ^ 1

Thats an extra multiplication there

We have to compute log3nlog⁡_3n powers of aa, computing each power requires 22 multiplications a=a×(a×a)a = a \times (a \times a) so thats 2log3n2log_3n multiplications for aa, and then we have to do at most 2log3n2log_3n multiplications to get the final answer.
The the final complexity of the algorithm is O(log3n)O(log_3n)

Implementation

long long ternpow(long long a, long long b) {
    long long r, res = 1;
    
    while (b) {
        r = b % 3;
        if (r == 2) res = res * a * a;
        else if (r == 1) res = res * a;
        a = a * a * a;
        b /= 3;
    }
    return res;
}

Recursive Definition:

an={1if n==0(an3)3if mod(n,3)==0(an13)3aif mod(n,3)==1(an23)3aaif mod(n,3)==2a^n = \begin{cases} 1 &\text{if } n == 0 \\ \left(a^{\frac{n}{3}}\right)^3 &\text{if } mod(n, 3) == 0\\ \left(a^{\frac{n - 1}{3}}\right)^3 \cdot a &\text{if } mod(n, 3) == 1\\ \left(a^{\frac{n - 2}{3}}\right)^3 \cdot a \cdot a &\text{if } mod(n, 3) == 2\\ \end{cases}

Computing abmodma^b \mod m

long long ternpow_mod(long long a, long long b, long long m) {
    a %= m;
    long long r, res = 1;
    while (b) {
        r = b % 3;
        if (r == 2) res = res * (a * a % m) % m;
        else if (r == 1) res = res * a % m;
        a = a * a % m * a % m;
        b /= 3;
    }
    return res;
}
long long binpow_mod(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1; // b /= 2
    }
    return res;
}

At their worst case the ternary version performs 4log3n4log_3n multiplications, while the binary version does 2log2n2log_2n multiplications, it can be easily shown that 4log3n>2log2n4log_3n > 2log_2n

Hence the binary version should be faster.