팩토리얼(factorial)의 소수 모듈로 곱셈의 역원(modulo inverse)을 구하는 기본적인 테크닉

이미 알고있는 것들인데 블로그에 정리가 안되어 있어서 1. n!을 소수 p로 나눈 나머지 소수 p에 대하여 $n! mod p$를 구하는 문제가 있다. 단 하나의 $n! mod p$를 구해야한다면... $n! = n*(n-1)*(n-2)*...*1$이므로, 1부터 n까지 $O(N)$에 다 곱한 다음, p로 나눈 나머지를 구하는 것이 간단하다. 하지만 n이 매우 크면서, 여러가지 n에 대한 $n! mod p$가 필요하다면 이야기가 달라진다. 여러가지 n에 대한 $n! mod p$가 필요하다면 가능한 모든 n에 대해 $n! mod p$를 구해놓고 O(1)로 접근하면 된다. 여기서 다이나믹 프로그래밍에 의해 이전에 구해놓은 값을 저장해둔다면, O(N)에 모든 n에 대해 $n! mod p$를 구할 수 있다. $n..