thopecoder's blog

Question: Calculate the remainder when p^(q!) is divided by r.
By thopecoder, history, 4 years ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +10 Vote: I do not like it

    $$$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...

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what if q! overflows? Can I just do q! % r ? Will the result of $$$p^{q! \% r}$$$ be same as $$$p^{q!}\%r$$$ ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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$$$

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +25 Vote: I do not like it

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)$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it +46 Vote: I do not like it

A simple loop would do the job:

for(int i=1; i<=q; i++)
	p = powM(p, i, r);
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

See this

→ Reply