합동식
대수학에서 합동식이란 숫자의 실제 크기를 불문하고, 어떤 수로 나누었을 때 나머지가 같은 수를 의미합니다.
페르마의 소정리
$a$가 정수이고 $p$가 소수이고 $p$가 $a$의 배수가 아닐 때 (즉, $a$가 임의의 소수 $p$의 약수가 아니므로, $a≠p$)
만약 $a$와 $p$가 서로소이면 $a^{p-1} ≡ 1 (mod \; p)$를 만족한다.
이항계수 $nCr$ 빠르게 구하기
주어지는 $n$과 $r$의 범위가 $O(nr)$의 시간과 공간 복잡도로 수행 가능하다면
$\binom{n}{r}$ = $\binom{n-1}{r-1}$ + $\binom{n-1}{r}$ 공식을 이용합니다.
그러나 $n$과 $r$이 10만 ~ 100만 정도의 범위에 있을 경우에는 위의 방식을 이용하지 못합니다.
이런 경우에는 항상 어떤 소수 $p$에 대한 나머지를 구하는 방식이므로
$\binom{n}{r}$ ≡ $n!$ / $(r!(n-r)!)$ $mod \; p$ 공식을 이용합니다.
여기서 페르마의 소정리를 이용하여 $r!(n-r)!$의 역원을 곱해줘야 합니다.
$a^{p-1} ≡ 1 (mod \; p)$을 만족하므로, $(mod \; p)$에 대해서 $a$의 역원은 $a^{p-2}$ 입니다.
따라서 $\binom{n}{r}$ ≡ $n!(r!(n-r)!)^{p-2}$ $(mod \; p)$을 만족합니다.
참고링크
페르마의 소정리와 활용
마크다운 수식 작성법 1
마크다운 수식 작성법 2
마크다운 수식 작성법 3
Jekyll 블로그에 MathJax로 수식 표현하기