페르마의 소정리를 활용한 알고리즘 문제 풀기

이 게시글에서는 페르마의 소정리를 간략하게 배우고 관련 알고리즘 문제를 푼다.

 

정수 a와 p가 있고 a가 p의 배수가 아니면서 p가 소수(Prime number)일 때 다음이 성립한다.

 

$a^{p} \equiv a (\mod p)$

 

여기서 $\equiv$ 는 합동을 의미하는 기호인데 $a^{p}$를 $p$로 나눈 나머지는 $a$를 $p$로 나눈 나머지와 같다는 뜻이다.

 

또한 여기서 양변에 a를 나누는 것으로 다음 두 식을 유도할 수 있다.

 

$a^{p - 1} \equiv 1 \; (\mod \; p)$

$a^{p - 2} \equiv a^{-1} \; (\mod \; p)$

 

페르마의 소정리에 대해 알았으니 이를 이용하는 문제를 하나 풀어보자.

 

icpc.me/16134

16134번: 조합 (Combination)

단순히 이항 계수를 구하는 문제이긴 한데 주어진 N이 너무 크다. 대신 $10^{9} + 7$ 로 나눈 나머지를 출력하라고 한다. 참고로 $10^9 + 7$은 소수다.

 

그렇다면 이렇게 큰 수의 이항 계수는 어떻게 구할까? 이항 계수 $\binom{N}{R}$를 팩토리얼로 나타내면 다음이 될 것이다.

 

$\binom{N}{R} =  \frac{N!}{R!(N - R)!} = N! \times (R!(N - R)!)^{-1}$

 

아 뭔가 보이는 것 같다. $(R!(N - R)!)^{-1}$ 를 주목해보자.

 

우리는 여기서 $10^9 + 7$로 나눈 나머지를 구해야 하므로 $(R!(N - R)!)^{-1} \; mod \, 10^9 + 7$ 이 될 것이다.

 

눈치챘는가? 우리는 여기에서 페르마의 소정리를 이용할 수 있다. 페르마의 소정리에 의해

 

$(R!(N - R)!)^{10^9 + 7 - 2} \equiv (R!(N - R)!)^{-1} \; (mod \; 10^9 + 7)$ 이 성립되므로 $(R!(N - R)!)^{10^9 + 7 - 2}$ 를 계산하기만 하면 되는 것이다.

 

물론 지수가 10억을 넘기므로 반복문으로 계산이 불가능하다. 분할정복 거듭제곱법으로 계산하자.

 

페르마의 소정리로 분모를 구했으니 분자와 곱해주기만 하면 이항 계수를 $10^9 + 7$로 나눈 나머지를 얻을 수 있다.

 

지금까지 페르마의 소정리를 알아보았다. 페르마의 소정리를 이용할 수 있는 문제들을 소개하면서 글을 끝마치겠다. 한번 풀어보자!

 

icpc.me/15791

atcoder.jp/contests/abc156/tasks/abc156_d