관련 코드는 github에서 찾아볼 수 있다.


이 글에서는 팩토리얼과 이항계수를 $n$으로 나눈 나머지를 계산하는 방법에 대하여 다룬다.

  • 중국인의 나머지 정리를 기반으로 한 아이디어는 여기서도 등장한다.
  • $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$에 대한 나머지를 구하려면, 각 $p_i^{e_i}$에 대한 나머지를 구하면 된다.
  • 그 후, 단순히 중국인의 나머지 정리를 사용하여 합쳐주면 된다. 그러니 문제를 prime power에 대해서만 해결하면 된다.

이 글에서 다룰 내용은 상당한 난이도를 갖는 강화판들이 있다. 이에 대한 것은 결과만 언급하고 링크를 걸겠다.


먼저 팩토리얼, 이항계수를 $p$로 나눈 나머지를 계산하는 방법을 알아보자. $p$는 소수.


팩토리얼


주제 1. 주어진 $n, p$에 대하여 $n! \pmod{p}$ 계산하기. 

단순히 $n! \pmod{p}$를 계산한다고 가정하자. $n \ge p$인 경우, 값은 $0$이다. 

그러니, $n < p$인 경우만 고려해도 충분하다. $n$이 작으면, $\mathcal{O}(n)$ 알고리즘이 자명하다.

$n, p$가 모두 $10^{9}$-scale로 큰 경우는, $\mathcal{O}(\sqrt{p}\log p)$ 시간에 해결할 수 있으나 상당히 어려운 문제다. 문제와 이 글 참고. 


주제 2. $1!, 2!, \cdots , n!$ 각각을 $p$로 나눈 나머지와 각각의 $\pmod{p}$에 대한 modular inverse 계산하기.

modular inverse를 계산하는 이유는 역시 이항계수를 계산하기 위해서이다. 이 주제는 수많은 카운팅 문제들에서 사용된다.

$1!, 2!, \cdots n!$ 각각을 $p$로 나눈 나머지는 점화식 $k! \equiv (k \cdot (k-1)!) \pmod{p}$를 이용하여 $\mathcal{O}(n)$ 시간에 계산할 수 있다.


팩토리얼들의 modular inverse를 구하는 것은 정말 여러 방법이 있다.

  • 방법 1. 우선 각각의 modular inverse를 그냥 구하는 방법이 있다. 확장 유클리드 알고리즘을 쓰면 된다. 이 경우 $\mathcal{O}(n \log p)$의 시간 소요.
  • 방법 2. $1, 2, \cdots, n$ 각각의 modular inverse를 $\mathcal{O}(n)$에 구하는 방법이 있다. 이를 사용하면 팩토리얼의 modular inverse도 똑같이 $\mathcal{O}(n)$에 ok.
  • 알고리즘의 설명을 위해 프로그래밍 같은 notation을 잠시 도입한다. $i$의 modular inverse를 $inv[i]$라 하고, $a$를 $b$로 나눈 나머지를 $a \% b$라 하자.
  • Fact. $2 \le i<p$이면, $inv[i] \equiv inv[p \% i] \cdot (p - \lfloor p/i \rfloor) \pmod{p}$가 성립한다. ($p$가 소수임이 필요하다)
  • 증명. $p = qi + r$이라 하자. $p \% i = r$이며, $\lfloor p/i \rfloor = q$이다.
  • 이제 $i \cdot inv[p \% i] \cdot (p - \lfloor p/i \rfloor) \equiv i \cdot inv[r] \cdot (p-q) \equiv inv[r] \cdot (-qi) \equiv inv[r] \cdot r \equiv 1 \pmod{p}$이므로 증명 끝.
  • 여기서 $p \% i < i$이며, $inv[1]=1$임을 생각하자. 위 Fact는 결국 $inv$ 배열을 채우기 위한 DP 식이 된다. 
  • $k!$의 modular inverse는 $(k-1)!$의 modular inverse와 $k$의 modular inverse를 곱해서 얻을 수 있다.
  • 방법 3. 매우 쉽고 똑똑한 아이디어다. $n!$의 modular inverse를 먼저 확장 유클리드 알고리즘으로 구하자.
  • 그 후, $k!$의 modular inverse가 $(k+1)!$의 modular inverse와 $(k+1)$의 곱임을 이용한다. 역순으로 계산하는 것이다.
  • 이 방법으로 $1, 2, \cdots n$ 각각의 modular inverse도 $\mathcal{O}(n)$ 시간에 구할 수 있다. 
  • $k$의 modular inverse를 구하려면, $k!$의 modular inverse와 $(k-1)!$을 곱하면 된다.

방법 2, 3은 둘 다 $\mathcal{O}(n)$ 알고리즘이다. 하나만 알아도 충분하지만, 극한의 시간 최적화가 필요한 경우에는 둘 다 알아야 한다.

  • 만약 $1, 2, \cdots , n$ 각각의 modular inverse를 얻는 것이 주요 목적이라면, 방법 2를 사용하는 것이 맞다.
  • 만약 $1!, 2!, \cdots, n!$ 각각의 modular inverse를 얻는 것이 주요 목적이라면, 방법 3을 사용하는 것이 맞다.
  • 위에서 언급한 modular inverse들을 전부 구하는 것이 목적이라면, 어느 것을 사용해도 문제가 없다.
  • 이유를 파악하기 위해서는 각 방법들이 언급한 값들을 계산하기 위해서 몇 번의 나머지 연산을 하는지 생각해보자.

개인적인 추천은 그냥 방법 2, 3을 다 알고 있는 것이다. 방법 2의 원리까지는 이해할 필요가 없으니, 코드만 알아두면 된다.


주제 3. $n! = p^e m$라고 쓸 경우 (단, $m$은 $p$의 배수가 아니다) $e$와 $m \pmod{p}$를 계산하기.

이는 일종의 "$n!$의 0이 아닌 마지막 자리 구하기"와 같은 부류의 문제라고 볼 수 있다. 이 문제를 $p$진법에서 푸는 것이기 때문.

이 문제가 필요한 이유는 이항계수의 계산이다. $n!$이 $p$의 배수라고 해서 $\binom{n}{k} =n!/(k!(n-k)!)$이 $p$의 배수일 이유는 없다.


$n < p$인 경우는 $e=0$이며, $m \pmod{p}$는 단순히 $n! \pmod{p}$이다. 그러니 앞선 논의를 그대로 사용할 수 있다.

사실 이 말은 주제 3의 문제가 주제 1의 문제를 포함하고, 더 어려운 문제라는 이야기다. 그러니 $p$가 크면 이 문제도 풀기 힘들 것이라고 예측할 수 있다.

여기서 다룰 경우는 $p$가 $\mathcal{O}(p)$ 알고리즘이 돌아갈 정도로 작고, $n$은 매우 클 수 있는 경우이다.


여기서도 문제를 축소하는 방법을 사용할 것이다. $n=pk+r$, $0 \le r < p$라고 하자. 아래 그림과 함께 보자.

  • $1$부터 $n$까지의 수 중, $p$의 배수가 아닌 것에 먼저 집중하자.
  • $[1, p-1], [p+1, 2p-1], \cdots , [p(k-1)+1, pk-1], [pk+1, pk+r]$ 형태의 구간으로 나누어 볼 수 있을 것이다.
  • 첫 $k$개의 구간을 보자. 각 구간에 있는 정수들을 곱한 값은 $(p-1)! \pmod{p}$이다. (사실 이는 $-1 \pmod{p}$다. 윌슨의 정리)
  • $[pk+1, pk+r]$의 구간에 있는 정수들을 곱한 값은 $r! \pmod{p}$이다. 
  • 이제 $p$의 배수들인 것에 집중하자. $p, 2p, \cdots , kp$가 있다. 여기서 $p$를 $k$개 뽑아낼 수 있다.
  • 그러면 남는 것은 $1, 2, \cdots , k$고, 이는 정확히 $k!$과 같다. 여기서 우리는 문제를 $k!$에 대한 문제로 축소시켰다.
  • $k!$을 $p^{e'} m'$으로 쓸 때, $e'$와 $m' \pmod{p}$의 값을 알아냈다고 가정하자. 이제 $n! = p^e m$이라 쓸 때 $e$와 $m \pmod{p}$를 구할 수 있을까?
  • 가능하다. 위 논의를 정리하면, $e = e' + k$, $m \equiv m' \cdot (p-1)!^k \cdot r! \pmod{p}$를 반환하면 된다.
  • 앞에서도 언급했지만 $(p-1)! \equiv -1 \pmod{p}$이므로, $m$을 계산할 때는 $k$의 홀짝성만 봐도 충분하다.
  • 당연히 구현은 재귀적으로 하는 것이 편하다. 또한, 알고리즘을 돌리기 전 $1!, 2!, \cdots , (p-1)! \pmod{p}$를 전처리하는 것이 좋다. 
  • 문제가 얼마나 축소되는가? : $n$에서 $k$로 축소시켰고, $k \le n/p \le n/2$이다. 그러니 반 이상 감소하고, 로그 시간에 ok.
  • 여러분도 눈치챘겠지만, 여기서 $e = \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \cdots $임을 얻는다.



이항계수


이제 이항계수 $\binom{n}{k}$를 $\pmod{p}$에 대하여 계산하는 방법을 보자. $\binom{n}{k} = \binom{n}{n-k}$이니, $k \le n/2$만 보자. 여러 경우가 있다.


Case 1. $k<p$이며 $k$가 작은 경우. 

이 경우, $\displaystyle \binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{1 \cdot 2 \cdots k}$임을 이용하여 직접 계산을 할 수 있다.

분자, 분모를 모두 $\pmod{p}$로 구한 후, 분모의 modular inverse를 구해 나눗셈을 곱셈으로 대체한다. 

물론, $k<p$이므로 $\text{gcd}(k!,p)=1$이며, 그러니 확장 유클리드 알고리즘으로 modular inverse를 구할 수 있다.

사실, $\displaystyle \binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1}$이 성립함을 이용하여 더 많은 것을 할 수 있다.

위 식을 차례대로 적용하여, 단순히 $\binom{n}{k} \pmod{p}$를 구하는 것이 아니라 $\binom{n}{0}, \binom{n}{1}, \cdots , \binom{n}{k}$ 각각을 $p$로 나눈 나머지를 구할 수 있다.


Case 2. 작은 $n, k$에 대하여 전부 전처리를 하고 싶은 경우.

이 경우, 파스칼의 삼각형을 이용하여 DP와 같은 방식으로 계산을 할 수 있다. 정수론이 필요없는 영역이다.


Case 3. $p$가 작은 경우, 즉 $\mathcal{O}(p)$ 알고리즘이 동작할 수 있는 경우.

먼저 $1!, 2!, \cdots , (p-1)!$ 각각을 $p$로 나눈 나머지와, 그들의 modular inverse를 전처리하자.


방법 1. Lucas 정리 사용

많이 사용되는 방법 중 하나다. 다음 결과를 증명하지 않고 제시한다. 증명은 위 링크에 걸려있다. 

정리. $m = m_km_{k-1} \cdots m_0$, $n=n_k n_{k-1} \cdots n_0$가 $m, n$의 $p$진법 전개라면, $\displaystyle \binom{m}{n} \equiv \binom{m_k}{n_k} \cdot \binom{m_{k-1}}{n_{k-1}} \cdots \binom{m_0}{n_0} \pmod{p}$다.

증명의 아이디어가 (Frobenius Endomorphism) 문제 풀이에 사용된 걸 본 적이 없는 것은 아니나, 모두 매우 어려운 문제들이다.

이 결과는 문제를 단순히 $m, n$이 $p$ 미만일 경우에 $\binom{m}{n} \pmod{p}$를 계산하는 문제로 만들어준다.

$m<n$인 경우 결과는 $0$이며, 그렇지 않은 경우 $m!/(n!(m-n)!)$을 계산하여 답을 얻을 수 있다.

이제는 어느 정도 당연한 이야기지만, 나눗셈은 modular inverse를 곱하는 것으로 계산한다.

전처리를 했기 때문에, 각 $\binom{m_i}{n_i} \pmod{p}$를 구하는 것에는 $\mathcal{O}(1)$의 시간이 필요하다.

그러니 시간복잡도는 $\mathcal{O}(k) = \mathcal{O}(\log_p m)$이 되겠다. 매우 빠르고 간단한 방법이다. 


방법 2. 앞서 다룬 주제 3 사용

주제 3을 이용하여도 문제를 해결할 수 있다. $\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}$이라 하자.

이제 $n! = p^{e_1} m_1$, $k! = p^{e_2} m_2$, $(n-k)!=p^{e_3} m_3$라고 쓰자. $m_1, m_2, m_3$는 $p$의 배수가 아니다.

이때, 주제 3에서 다룬 알고리즘으로 $e_1, e_2, e_3$와 $m_1, m_2, m_3 \pmod{p}$를 로그 시간에 계산할 수 있다.

그러면 이제 $\displaystyle \binom{n}{k} =  p^e m$이라 쓸 때, $e$와 $m \pmod{p}$를 구할 수 있을까?

있다. $e = e_1 - e_2 - e_3$, $m \equiv m_1 (m_2m_3)^{-1} \pmod{p}$가 성립하기 때문이다. $a^{-1}$은 $a$의 잉여역수.

만약 $e>0$이라면 주어진 이항계수는 $p$의 배수가 된다. 그렇지 않다면, 이항계수를 $p$로 나눈 나머지는 $m \pmod{p}$와 같다. 끝.


이제 $\pmod{p}$의 논의를 끝냈다. 이제 본격적으로 prime power에 대하여 논의해보자. 


팩토리얼


주제 1. 주어진 $n, p$에 대하여 $n! \pmod{p^e}$ 계산하기.

$n \ge pe$이면 $n!$에서 $p$의 배수가 $e$개 이상 들어가므로, $n! \pmod{p^e}$는 $0$이 된다. 

$n$이 작으면 단순한 $\mathcal{O}(n)$ 알고리즘이 작동한다는 점은 기존 주제 1의 논의에서와 동일하다. 


주제 2. $1!, 2!, \cdots , n!$ 각각을 $p^e$로 나눈 나머지와 각각의 $\pmod{p^e}$에 대한 modular inverse 계산하기.

문제가 잘 정의되려면 역시 $n < p$를 가정해야 한다. 이 경우, 방법 1과 방법 3이 잘 적용된다. 


주제 3. $n! = p^t m$라고 쓸 경우 (단, $m$은 $p$의 배수가 아니다) $t$와 $m \pmod{p^e}$를 계산하기.

$t$를 계산하는 것은 기존 주제 3과 애초에 목표가 동일하다. $m \pmod{p^e}$를 계산하는 것이 목표. 이 역시 기존 주제 3과 비슷한 방법으로 할 수 있다.

  • 쉽게 가자. $n=pk+r$, $0 \le r < p$라고 쓰자. 
  • $1$부터 $n$까지의 수 중, 이번에는 $p$의 배수인 것에 먼저 집중해보자.
  • 여기서는 $p$가 $k$개 추가되고, $k!$이 튀어나온다. 이는 문제의 "축소"된 형태이다. 여기까진 기존 주제 3과 동일.
  • 이제 $p$의 배수가 아닌 것을 봐야 한다. 잠시 $n=p^ek' + r'$이라고 하자. $0 \le r' < p^e$. 
  • $\mathcal{O}(p^e)$의 시간을 투자하여, DP를 이용해 다음 배열 $val[i]$를 ($0 \le i < p^e$) 채워놓자. 미리 전처리하는 것이다.
  • $val[i]$ : $1$ 이상 $i$ 이하 자연수 중 $p$의 배수가 아닌 것을 곱한 값을 $p^e$로 나눈 나머지.
  • $[1, p^e-1]$ 중 $p$의 배수가 아닌 것부터 $[p^e(k'-1)+1, p^ek'-1]$ 중 $p$의 배수가 아닌 것이 먼저 있을 것이다.
  • 그 후 $[p^ek'+1, p^ek'+r']$ 중 $p$의 배수가 아닌 것이 여기에 있다. 이를 모두 종합하면?
  • $val[p^e-1]^{k'} \cdot val[r'] \pmod{p^e}$이라는 값이 튀어나온다. 결국 기존 주제 3과 거의 다를 바가 없다. 
  • 또한, $val[p^e-1]$이 $\pmod{p^e}$로 $1$ 또는 $-1$이라는 결과 역시 알려져 있다. 그러니 $k'$의 홀짝성만 봐도 ok.

이 알고리즘은 $\mathcal{O}(p^e)$ 급의 계산이 필요하다. 하지만 실제로는 $\mathcal{O}(pe)$ 급으로 계산이 가능하다. 매우 어렵다.

이 강화된 알고리즘을 공부하고 싶다면, HYEA님의 이 글과 원본이라고 볼 수 있는 min_25의 이 글을 보자.


이항계수

여전히 $k \le n/2$만 보는 아이디어는 유효하다.


Case 1. $k<p$이며 $k$가 작은 경우. 

이 경우, $1, 2, \cdots , k$ 각각의 $\pmod{p^e}$에 대한 modular inverse가 존재하므로 아이디어가 그대로 적용된다.


Case 2. 작은 $n, k$에 대하여 전부 전처리를 하고 싶은 경우.

이 경우, 파스칼의 삼각형을 이용하여 DP와 같은 방식으로 계산을 할 수 있다. 정수론이 필요없는 영역이다.


Case 3. $p$가 작은 경우, 즉 $\mathcal{O}(p^e)$ 또는 $\mathcal{O}(pe)$ 알고리즘이 동작할 수 있는 경우.

이 문제를 Lucas 정리로 풀려고 하면 (즉, Lucas 정리의 확장판을 찾으려 한다면) 상당히 고생할 것이다. 적어도 내 기억은 즐겁지 않았다.

하지만 주제 3을 이용한 풀이를 생각한다면, 기존 Case 3과 완전히 동일한 풀이가 적용된다. 주제 3을 여기에 수록한 이유다.

 


이제 $\pmod{p^e}$에 대한 이야기를 끝냈으니, 이론적으로 모든 내용을 다 했다. 하지만 몇 가지 더 이야기거리가 남았다.

  • 중국인의 나머지 정리는 항상 강조하지만 수학에서나 정수론 알고리즘에서나 매우 중요한 결과고 쓸모도 많다.
  • 하지만 이걸 제대로 써먹으려면 (즉, prime power로 문제를 쪼갠 후 다시 합치는 방식을 적용) 소인수분해를 해야 한다.
  • 기본적으로 소인수분해는 매우 어려운 문제다. CP/PS 환경에서는 보통 커봐야 $2^{64}$인 수를 다루니 Pollard-Rho 알고리즘을 배우면 조금 낫다.
  • 하지만 Pollard-Rho가 엄청 빠른 알고리즘인 것도 아니다. 즉, 일반적인 $\pmod{M}$에 대해서 사용할 수 있는 알고리즘을 더 다룰 필요가 있다.
  • 당연한 것이지만 아래에서 다룰 "일반적인 알고리즘"은 위에서 다룬 $\pmod{p}$, $\pmod{p^e}$의 경우에서도 사용할 수 있다. 
  • 아래에서 다룰 알고리즘들은 modulus가 갖는 소인수 $p$나 prime power $p^e$의 크기 등에 영향을 받지 않는다.

팩토리얼


주제 1. $\mathcal{O}(n)$ 알고리즘은 당연히 아직도 유효하다.

주제 2. 팩토리얼만 구하는 $\mathcal{O}(n)$ 알고리즘은 당연히 아직도 유효하다.

modular inverse를 전부 구하는 문제가 잘 정의되려면 $1, 2, \cdots , n$이 전부 $M$과 서로소여야 한다.

이 경우, 방법 1, 3이 잘 적용된다. (소수, 소수의 거듭제곱 여부를 사용한 적이 없다)

주제 3. 일반적인 modulus $M$에 대해서 논의하기 애매한 주제다. 이 때문에 이항계수를 계산하기가 어렵다.


이항계수

Case 1. $k$가 작고, $1, 2, \cdots , k$ 전부가 $M$과 서로소인 경우.

이 경우에는 기존 알고리즘을 그대로 적용할 수 있다. $\pmod{M}$에 대한 modular inverse를 취할 수 있기 때문이다.

Case 2. 파스칼의 삼각형을 그대로 적용할 수 있다. 이미 말했지만, 이 부분은 정수론이 아니라 DP에 가깝다.

Case 3. 하기 힘들다. 애초에 각 소수가 작다는 가정이 전제되는 만큼, 소인수분해가 필요하다.

Case 4. 특수한 경우를 하나 더 소개한다. 바로 $n, k$가 둘 다 적당히 작은 경우다.

이 경우, 앞서 소개한 에라토스테네스의 체를 이용한 로그 시간 소인수분해를 하여 문제를 해결할 수 있다.

즉, $1, 2, \cdots , n$ 전부를 소인수분해 할 수 있으니, $\displaystyle \binom{n}{k} = \frac{n \cdot (n-1) \cdots \cdot ( n-k+1)}{1  \cdot 2 \cdots \cdot k}$ 역시 그 분모/분자를 전부 소인수분해 할 수 있다.

이를 통해서 아예 $\displaystyle \binom{n}{k}$의 소인수분해를 얻을 수 있다. 이제 나눗셈에 대한 걱정이 아예 없으니, 단순 계산이 가능해진다. 끝.

  1. Sait2000 2020.12.30 18:29

    "일반적인 알고리즘"에서 팩토리얼의 주제 2에서 방법 2가 안 된다는 내용이 빠져있네요... p^e에는 써놓으셨는데.

  2. Sait2000 2021.02.08 14:24

    팩토리얼의 주제 3번에 대해서 필요한 n의 최댓값 < p^e라면 n 즈음의 시간에 계산이 된다는 사실도 적혀 있으면 좋겠네요

    • rkm0959 2021.02.08 14:27 신고

      사용하는 티스토리 에디터를 바꾸면서 수정하기가 되게 힘들어졌어요 ㅜㅜ

  3. 승욱은 2021.12.16 14:18 신고

    또한, val[pe−1]이 (modpe)로 1 또는 −1이라는 결과 역시 알려져 있다. 그러니 k′의 홀짝성만 봐도 ok


    혹시 이 부분에서 val[p^e -1] (mod p^e) 가 1이고 k'이 홀수면 어떻게 해야하나요..?

    • rkm0959 2021.12.20 10:20 신고

      val[p^e-1]^k'을 계산하기 위해서 val[p^e-1]^(k' mod 2)를 사용해도 된다는 의미였습니다