| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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?
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