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?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Edit: I'm sorry, but I noticed that my approach is wrong.
$$$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...
I just noticed the beginner mistake in my algebra..
what if q! overflows? Can I just do
q! % r? Will the result of $$$p^{q! \% r}$$$ be same as $$$p^{q!}\%r$$$ ?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$$$
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)$$$.
A simple loop would do the job:
See this