Lucas' Theory (1) 썸네일형 리스트형 53. Lucas' Theorem 뤼카 정리(루카스 정리, Lucas' Theorem)는 이항계수 $_n\mathrm{C}_r$을 소수 $p$로 나눈 나머지를 구할 때 사용되는 정리이다. 이 정리를 이용하면 $n$과 $r$이 클 때에도 이항계수를 빠르게 구할 수 있다. 정리의 내용은 다음과 같다. $$_n\mathrm{C}_r=(_{\lfloor n/p \rfloor}\mathrm{C}_{\lfloor r/p \rfloor})(_{n\,\bmod\,p}\mathrm{C}_{r\,\bmod\,p})\bmod p$$ 만약 $n 이전 1 다음
