### thopecoder's blog

By thopecoder, history, 6 weeks ago,

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?

• +6

 » 6 weeks ago, # | ← Rev. 2 →   +8 Edit: I'm sorry, but I noticed that my approach is wrong.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +10 $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...
•  » » » 6 weeks ago, # ^ |   0 I just noticed the beginner mistake in my algebra..
•  » » 6 weeks ago, # ^ |   0 what if q! overflows? Can I just do q! % r ? Will the result of $p^{q! \% r}$ be same as $p^{q!}\%r$ ?
•  » » » 6 weeks ago, # ^ |   0 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$
 » 6 weeks ago, # |   0 this was a kickstart problem,I don't remember which year
 » 6 weeks ago, # | ← Rev. 3 →   +25 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)$.
 » 6 weeks ago, # |   0 is r prime?? if r is prime then apply fermats theorom
 » 6 weeks ago, # |   +46 A simple loop would do the job: for(int i=1; i<=q; i++) p = powM(p, i, r); 
•  » » 6 weeks ago, # ^ |   0 nice. Didn't think of this.
 » 6 weeks ago, # |   0
•  » » 6 weeks ago, # ^ |   0 thanks!
 » 2 weeks ago, # |   0 There would be exactly r different remainders for pq! % 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] = pi % 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).