-
이항계수의 빠른 계산
서론 $\binom{N}{K}$ 는 $N$개의 구분이 되는 물체 중 $K$개를 고르는 가짓수이고, 이를 이항계수라고 부른다. 이항계수는 한 조합론적 상황에서 많이 사용된다. 이 $\binom{N}{K} = \dfrac{N!}{K!(N-K)!}$임이 잘 알려져 있다. 이 수를 소수가 아닌 임의의 수 $M$으로 나눈 나머지를 구하는 방법에 대해서 알아본다. Naive 이항계수를 $M$으로 나눈 나머지를 구하는 가장 쉬운 방법은 실제로 $N!$을 그냥 1부터 $N$까지의 모든 수를 곱하는 것으로 계산하는 것이다. 하지만 이럴 경우에 나눗셈이 잘 되지 않는다. 예를 들어서, $M=9$인 경우에는, $6! = 720$과 $7!=5040$을...
-
N! mod P 의 빠른 계산
서론 $N!$ 은 1이상 $N$ 이하의 모든 정수를 곱한 수 이다. 이 $N!$는 다양한 조합론적 상황에서 많이 사용된다. 이 $N!$을 특정한 소수 $P$로 나눈 나머지를 빠르게 ($O(\sqrt{N} \log{N})$ 시간에) 계산 하는 방법에 대해서 알아본다. Naive 팩토리얼을 구하는 가장 쉬운 방법은 모든 1이상 $N$ 이하의 수를 곱해서 $P$ 로 나누는 것이다. $ab$를 $P$로 나눈 나머지와 $(a \bmod P)(b \bmod P) \bmod P$ 가 같다는 것을 이용하면, 사이에 나오는 숫자를 항상 $P^2$ 이하로 유지하면서 쉽게 구할 수...