Lucas' Theorem
2015. 7. 25. 00:14ㆍ알고리즘 문제풀기/정수론
For a prime number \(p\), Let
m=mkpk+mk−1pk−1+…+m0p0,
n=nkpk+nk−1pk−1+…+n0p0
where \(0 \leq m_{i}, n_{i} < p\)
\dbinom{m}{n} \equiv \displaystyle{\prod_{i=0}^{k}} \dbinom{m_{i}}{n_{i}} \mod p
'알고리즘 문제풀기 > 정수론' 카테고리의 다른 글
GCD & Extended Euclidean Algorithm (1) | 2016.08.09 |
---|---|
Miller-Rabin 소수 판정법 (0) | 2015.12.05 |
Modular Inverse (0) | 2015.07.23 |
빠른 거듭제곱 (1) | 2015.07.18 |