CSES Problem

https://cses.fi/problemset/task/1712/

Above is the link to the question.
My approach is

Its getting TLE verdict.
I believe the complexity of the above code is O(c*log b).
It would be really helpful if someone can provide me with a better solution :).

Consider Fermat’s little theorem: a^{p - 1} = 1 for a prime p and any a. In this problem, p = 10^9 + 7. So if you have some k where you want a^k and k \geq p - 1, you can just subtract p - 1 until you get a k < p - 1 (because that extra a^{p - 1} will contribute nothing). Equivalently, you can just take k \mod (p - 1).

What that means is you can compute b^c \mod (10^9 + 6), then compute a to the power of that, both with fast exponentiation. Complexity is O(n\log{p}) (or O(\log{p}) per test case).

2 Likes

Thanks , it was an elegant one :).