[알고리즘] 뤼카의 정리 (Lucas' Theorem)

정수론, 조합론

 

[알고리즘 소개]

음이 아닌 정수 n, k와 작은 소수 p에 대해 빠르게 $\dbinom{n}{k} \, mod \; p$를 구하는 알고리즘

 

---

[정리 소개]

n과 k를 p진법으로 나타낸 표기가

 

 $n = n_mp^m + n_{m-1}p^{m-1} + \cdots + n_1p^1 + n_0$

 $k = k_mp^m + k_{m-1}p^{m-1} + \cdots + k_1p^1 + k_0$

 

위와 같을 때,

 

$\dbinom{n}{k} \equiv \Pi_{i = 0}^{m} \dbinom{n_i}{k_i} (mod \; p)$

 

---

[코딩 방법]

1. 파스칼의 삼각형을 이용하여 $p * p$크기의 배열 dist에 이항 계수를 전부 저장
2. n과 k를 p진법으로 변환하면서 dist[$n_i$][$k_i$]를 계속 곱하고 p로 나머지 연산을 계속 반복
3. p진법으로 변환하는 과정에서 n 혹은 k가 0이 되면 반복을 종료 (진법 변환: codingdojang.com/scode/458)
4. n이 0이 된다면 뒤의 모든 경우는 $\dbinom{0}{k_i} = 1$이므로 결과값에 변화가 없음 ($x * 1 = x$)
5. k가 0이 된다면 뒤의 모든 경우는 $\dbinom{n_i}{0} = 1$이므로 결과값에 변화가 없음 ($x * 1 = x$)

---

[시간 복잡도]

$O(p^2)$

 

---

[공부용 링크]

bowbowbow.tistory.com/2