Hello Codeforces How to calculate pow(a,nCr) % p efficiently? Here 1 <= n <= 10^6, 1 <= r <= 10^6 and 1<= a <= 10^6
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3976 |
| 2 | tourist | 3815 |
| 3 | jqdai0815 | 3682 |
| 4 | ksun48 | 3614 |
| 5 | orzdevinwang | 3526 |
| 6 | ecnerwala | 3514 |
| 7 | Benq | 3482 |
| 8 | hos.lyric | 3382 |
| 9 | gamegame | 3374 |
| 10 | heuristica | 3357 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | -is-this-fft- | 165 |
| 3 | Um_nik | 161 |
| 3 | atcoder_official | 161 |
| 5 | djm03178 | 157 |
| 6 | Dominater069 | 156 |
| 7 | adamant | 154 |
| 8 | luogu_official | 152 |
| 9 | awoo | 151 |
| 10 | TheScrasse | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2025 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 15.01.2025 18:26:30 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
Sorry, i got it wrong
Hint: Use Legendre's formula and Fermat's little Theorem.
To find a^b %m when b is too large, we calculate a^(b%(m-1))%m this can be proceed using fermat little theorem.
To calculate nCr%(m-1) you can use chinese remainder theorem if m-1 is non prime and square free.
I prove a^b %m= a^(b%(m-1))%m in this way, but I am not sure whether it is correct or not.
Fermat's little theorem tells that a^(m-1) %m=1, and thus we can write b=x*(m-1)+y. Then, a^b %m=a^(x*(m-1)+y) %m= a^y * (a^(m-1))^x %m= (a^y %m) * (a^(m-1) %m)^x=a^y %m =a ^ (b%(m-1)) %m.
If this is correct, I really have never considered using Fermat's little theorem in this manner... My first reaction is to calculate the inverse of b when we need to compute a/b %m. Thank you so much for sharing such wonderful idea and extending my thought.
Can you elaborate more on how you calculte nCr%(m — 1) using chinese remainder theoreom ? Suppose that (m — 1) is non-prime.