Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

vignesh_in_zone's blog

calculate the mod of Exponential factorical

By vignesh_in_zone, history, 6 years ago, In English

given three numbers p , q, r calculate the pow( p , q!) % r

It would also be helpful if you could mention the important concepts needed in solving this problem ,

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

If $$$p$$$ and $$$r$$$ are relatively prime you use Euler's theorem $$$p^{\phi(r)} = 1$$$ mod $$$r$$$. So you need to calculate $$$q!$$$ mod $$$\phi(r)$$$. $$$\phi$$$ is the Euler totient function, for a prime $$$r$$$ it is just $$$r-1$$$. You can find the answer even if $$$(p, r) \gt 1$$$, but it involves additional steps.

→ Reply