You can split the problem into chunks, where each chunk has the same exponents all the way through. It doesn't get you O(1), but it gets you O(log(n)).