While helping out a friend on some CSES exponentiation problem, I came up with this humorous way to compute fast exponentiate:

So you see, the standard way to go about this sort of problem is to use binary exponentiation. But sometimes when there is a log based solution, there is a somewhat similar sqrt solution.

Binary exponentiation works by breaking up the input i into maximally sized powers of two. What if we break up somehow into something involving sqrtn? If we precompute all the powers:

and the powers

then we can compute any arbitrary exponent in O(1).

Is this ever useful? Probably not :P

#include <iostream>

using LL = long long;

constexpr int sz = 2<<15,
              m = 1e9 + 7,
              p = 2;

LL small[sz], large[sz];

void precomp(){
    small[0] = 1, large[0] = 1;
    for(int i=1; i<sz; ++i) small[i] = small[i-1] * p % m;
    for(int i=1; i<sz; ++i) large[i] = large[i-1] * small[sz-1] % m;
}

int pow(int i){
    return small[i & (sz-1)] * large[i / sz] % m;
}

int main(){
    precomp();

    std::cout << pow(13) << pow(3242)
              << pow(13426) << pow(234253234)
              << '\n';
}

Also: I believe it's possible to precompute with constexpr. This would be pretty funny.

tags: programming