Given three integers p,q,r. You have calculate remainder when $$$p^{(q!)}$$$ is divided by r. where '!' is factorial.

basically $$$p^{(q!)}$$$%r

constraints: `1 <= p,q,r <= 10^5`

I have tried using naive factorization with binary exponentiation. Is there a more optimized approach for this problem?

Edit: I'm sorry, but I noticed that my approach is wrong.

$$$p^a*p^b\neq p^{ab}$$$

Presumably it's better to start with $$$p$$$, raise it to the $$$1$$$ st power, then the $$$2$$$ nd, etc...

I just noticed the beginner mistake in my algebra..

what if q! overflows? Can I just do

`q! % r`

? Will the result of $$$p^{q! \% r}$$$ be same as $$$p^{q!}\%r$$$ ?Not really, take for example $$$p = 2, q = 3, r = 5, q! = 6, 2^6 = 64 = 4 (mod 5)$$$ while on the other hand $$$3! = 1 (mod 5), \text{ and } 2^1 = 2$$$

this was a kickstart problem,I don't remember which year

By an extension of Euler's theorem, $$$p^q\equiv p^{q\bmod\varphi(r)+\varphi(r)}\pmod r$$$.

Then, factorize $$$r$$$ to calculate $$$\varphi(r)$$$, in $$$O(\sqrt r)$$$.

Since $$$q!\bmod\varphi(r)$$$ can be calculated in $$$O(\sqrt q\log q)$$$, the total complexity is $$$O(\sqrt q\log q + \sqrt r)$$$.

is r prime?? if r is prime then apply fermats theorom

A simple loop would do the job:

nice. Didn't think of this.

See this

thanks!

There would be exactly r different remainders for p

^{q!}% r. And After a particular remainder reappears, then its easy to spot that there would be a cycle of all the current remainders ahead. And then the only thing you would have to do is find how many more p's you need to take.For example : Let p=2, q=3, r=5. Then lets keep a remainder array

`rem`

.where rem[i] = p

^{i}% r. so (assuming 1 based indexing) rem[1] = 2, rem[2] = 4, rem[3] = 3, rem[4] = 1.Now notice that rem[5] = 2 which has already been visited as a remainder. And hence there would be a cycle of these 4 numbers.

indexing = [1, 2, 3, 4].

`rem`

= [2, 4, 3, 1]. Now you only need to find how many p's we take and that is q!. And therefore since the size of the cycle is 4, our answer is rem[

`q!%4`

+1].(plus one because of the 1-based indexing).