My solution was a bit complicated, the code of the other accepted submission looked really simple, I'm yet to spend time and see what exactly is happening in that solution.

Anyway, I'll explain mine. Remove the corner cases, the solve(base,a,b,n,offset) is trying to return base^((a^b)-offset) % n. First I check if (a^b)==offset by taking log, and then returning 1 if it is, as I don't want to keep increasing offset and go to negative powers. Now, if gcd(base,n)==1. I apply fermat-euler theorem, and I can take ((a^b)-offset) % phi(n), phi is the euler totient function, and then do regular exponentiation. In the other case when they're not coprime, Let's assume gcd(base,n) is g. so I know the answer is definitely going to be a multiple of g. I take it out as common, and I'm left with g * ( g ^ ((a^b)-(offset+1)) * (base/g) ^ ((a^b)-offset) ) % (n/g), which is basically two recursive calls to the same function with modulo reduced by at least 2. Note that (base/g) part will not go any further in recursion, since it now has gcd(base/g,n/g)=1, So effectively the recursion goes ahead one step, dividing the modulo by at least 2. Hence, the recursion goes logn steps in depth, and all other parts are simply exponentiation.