백준 온라인 저지 - 14854. 이항 계수 6

https://www.acmicpc.net/problem/14854

14854번: 이항 계수 6

$_n C _k \:\operatorname{mod}\: 142857$을 빠르게 계산해야하는 문제. $142857 = 3^3 \times 11 \times 13 \times 37$으로 합성수라는 점에서 난이도가 상승했다. 

 

 

(풀이)

우선 $_n C _k$를 $27$, $11$, $13$, $37$로 나눈 나머지를 구하고 나면, 중국인의 나머지 정리를 이용해서 본 문제를 해결할 수 있음을 안다.

 

두 함수를 정의한다. 소수 $p$와 자연수 $x$에 대해,

$$ k_p(x) = \max\{ k \in \mathbb{Z} : p^k | x \} \\ r_p(x) = \frac{x}{p^{k_p(x)}} $$

으로 정의한다. 즉, $r_p(x)$와 $p$는 서로소이다.

 

$k_p(x!)$를 계산하는 방법은 굉장히 잘 알려져 있다.

$$ k_p(x!) = \lfloor x / p \rfloor + \lfloor x / p^2 \rfloor + \lfloor x / p^3 \rfloor + \cdots $$

왜냐하면 $1$부터 $x$까지 자연수 중 $p$를 약수로 가지는 수의 개수는 $\lfloor x / p \rfloor$, $p^2$을 약수로 가지는 수의 개수는 $\lfloor x / p^2 \rfloor$, ... 이기 때문이다.

 

$_n C _k = \frac{n!}{k! (n-k)!}$ 이기 때문에,  $k_p(n!) > k_p(k!) + k_p((n-k)!)$ 이면 $_n C _k$를 $p$로 나눈 나머지는 $0$ 이다.

그렇지 않다면 $r_p(n!)$, $r_p(k!)$, $r_p((n-k)!)$을 $p$로 나눈 나머지와 모듈러 역 연산을 이용해서 구할 수 있다.

 

$r_p(x!) = r_p(1) \cdot r_p(2) \cdot r_p(3) \cdots r_p(x)$ 이다.

$r_p(x)$를 $p$로 나눈 나머지가 주기성을 가짐을 알면 문제를 어렵지 않게 해결할 수 있다.

$$ \begin{align*} r_p(x!) &\equiv r_p(1) \cdot r_p(2) \cdot r_p(3) \cdots r_p(x) \\ &\equiv \left( r_p(1) \cdot r_p(2) \cdots r_p(p) \right) \left( r_p(p+1) \cdot r_p(p+2) \cdots r_p(2p) \right) \cdots \\ &\equiv \left( r_p(1) \cdot r_p(2) \cdots r_p(p-1) \cdot r_p(p) \right) \left( r_p(1) \cdot r_p(2) \cdots r_p(p-1) \cdot r_p(2p) \right) \cdots \left( r_p((x \:\operatorname{mod}\: p)!) \right) \\ &\equiv r_p(p!)^{\lfloor x / p \rfloor} \cdot r_p(\lfloor x / p \rfloor!) \cdot r_p((x \:\operatorname{mod}\: p)!) \:\operatorname{mod}\: p \end{align*} $$

윌슨의 정리에 의해 소수 $p$에 대해, $r_p(p!) \:\operatorname{mod}\: p = p - 1$ 임을 이용하고, $x \geq p$ 인 경우에 한해서는 재귀식으로, $x < p$ 일 때는 직접 계산하는 방식으로 $r_p(x!)$을 빠르게 구할 수 있다.

 

문제는 $27 = 3^3$ 으로 나눈 나머지를 구하는 경우이다. $27$이 소수가 아니기 때문에 다른 접근이 필요하다. 정확히는 $r_3(n!), r_3(k!), r_3((n-k)!)$을 $27$로 나눈 나머지가 필요하다.

$r_3(x!)$을 $27$로 나눈 나머지를 구해보자. $1$부터 $x$까지 자연수 중, $3$으로 나누어 떨어지는 수와 그렇지 않은 수로 구분해서 생각하면 아래와 같이 식 전개가 가능하다.

$$ \begin{align*} r_3(x!) &\equiv r_3(1) \cdot r_3(2) \cdot r_3(3) \cdots r_3(x) \\ &\equiv \left( r_3(1) \cdot r_3(2) \cdot r_3(4) \cdot r_3(5) \cdots r_3(25) \cdot r_3(26) \right) \cdots \left( r_3(3) \cdot r_3(6) \cdots r_3(3 \cdot \lfloor x / 3 \rfloor) \right) \\ &\equiv \left( r_3(1) \cdot r_3(2) \cdot r_3(4) \cdot r_3(5) \cdots r_3(25) \cdot r_3(26) \right)^{\lfloor x / 27 \rfloor} \cdot r_3(\lfloor x / 3 \rfloor !) \cdot r_3^* (x \:\operatorname{mod}\: 27) \\ &\equiv r_3^*(27)^{\lfloor x / 27 \rfloor} \cdot r_3(\lfloor x / 3 \rfloor !) \cdot r_3^*(x \:\operatorname{mod}\: 27) \:\operatorname{mod}\: 27 \end{align*} $$

단, $r_3^*(x)$ 는 $1$부터 $x$까지 $3$과 서로소인 모든 자연수의 곱으로 정의한다.

 

이제 $n!$, $k!$, $(n-k)!$을 각각 $27$, $11$, $13$, $37$로 나눈 나머지를 안다. 중국인의 나머지 정리를 이용하면 된다.