Hello, Codeforces! Today I've faced the following problem: is it possible to calculate N! modulo M (M is prime) in polynomial (relative to length of M) time? I thought it would be pretty popular problem, but I couldn't google anything useful. Does anybody know such algorithm or proofs that it does not exist?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
15:25:57
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
15:25:57
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 02:09:03 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
You can try this algo, if M is not too large.
Thanks, but I'm just curious if the polynomial algorithm exists.
Actually, you can calculate $$$n! \bmod p$$$ in $$$O(\sqrt{p} \log p)$$$.
See this paper Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator for more details.
wrong
а)
polynomial (relative to length of M) time.
if $$$N>=M$$$ then $$$N!$$$ $$$mod$$$ $$$M$$$ $$$=$$$ $$$0$$$.
Else calculate it in $$$O(N)$$$ :P
Am I missing something?
Maybe your's is not in Length of m complexity.
Then my questions is what is length of m? Can you please define it?
Is this no of digits in M?
Maybe saying $$$O(logM) == O(logM/log10)$$$ would have been better.
I think so. He may want the solution to be in O(log m).blyat can you confirm?
Yes, I want solution to be in O(log^k m) for some k.
This is the problem you are describing, maybe with few extra constraints: https://www.spoj.com/problems/BORING/en/
maybe with few extra constraints
Extra constraints sometimes make life easier.
Notice the constraint Abs(N-P) < 10^4.
Lemma — $$$(P-1)! \% P = 1$$$.
If the only solns of $$$x^2\%P=1$$$ are $$$-1,1$$$ for prime $$$P$$$ then this lemma holds. $$$(P-D)! \% P = (-1)^{(D-1)}*(P-1)! / (D-1)! \% P$$$
If I'm not mistaken this shall be the problem (even though the constrains are solvable with approach suggested by zimpha ==> so not polynomial in length ^_^ )