Here's the problem from LightOJ.

It says to calculate sod(n) [sum of digits of n] while n >= 10.

Here n = a^b, (0<= a,b <= 10^50,000 and a+b>0 )

I got the solution idea from this cf post.

It can be proven that the repeated digit sum of N is 1 + (N - 1) mod 9, so we basically need to calculate a^b mod 9.

It is well known that a^b ≡ a^b mod φ(M) (mod M) for (a, M) = 1

we need a and M to be co-prime. But when a is divisible by 3 then a and M will not be co-prime.

So when a will be divisible by 3 then we need to calculate this case separately.

Now a and M are co-prime and we can easily calculate a^b using the formula.

Accepted Solution Link