정수론
[알고리즘 소개]
이항 계수를 충분히 큰 소수로 나눈 나머지를 빠르게 구하는 알고리즘
[설명]
- 페르마의 소정리를 적용하기 위해 k!과 소수 p가 서로소여야 하므로 p가 k의 최댓값보다 큰 소수여야 함
- 페르마의 소정리: kangwlgns.tistory.com/47
[코딩 방법]
- $\dfrac{n!}{(n - k)!}$ 부분은 곱하고 나머지 연산을 반복
- $\dfrac{1}{k!}$ 부분은 페르마의 소정리에 의해 $k!^{(p - 2)}$와 동치
- k!을 곱하고 나머지 연산을 반복
- $k! % p$를 p - 2번 거듭제곱 (분할정복을 이용한 거듭제곱 사용: kangwlgns.tistory.com/44)
- 얻어진 $\dfrac{n!}{(n - k)!}$의 결과와 $k!^{(p - 2)}$의 결과를 곱하고 다시 나머지 연산
[시간 복잡도]
$O(k\,logp)$
[공부용 링크]
'정리 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 크루스칼 (Kruskal) (0) | 2021.04.05 |
|---|---|
| [알고리즘] 뤼카의 정리 (Lucas' Theorem) (2) | 2021.03.27 |
| [알고리즘] 파스칼의 삼각형 (Pascal's Triangle) (0) | 2021.03.26 |
| [알고리즘] 분할 정복을 이용한 거듭제곱 (0) | 2021.03.25 |
| [알고리즘] 유클리드 호제법 (Euclidean Algorithm) (0) | 2021.03.25 |