thopecoder's blog

By thopecoder, history, 5 weeks 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

»
5 weeks 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.

  • »
    »
    5 weeks 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...

  • »
    »
    5 weeks 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$$$ ?

    • »
      »
      »
      5 weeks 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$$$

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks 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)$$$.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks 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);
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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