Блог пользователя thopecoder

Автор thopecoder, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    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...

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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$$$

»
4 года назад, # |
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)$$$.

»
4 года назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

A simple loop would do the job:

for(int i=1; i<=q; i++)
	p = powM(p, i, r);
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится