====== 팩토리얼 ======
  * n이 조금만 커져도 정수형 범위를 넘어간다.
  * 실용적인 경우에는 스털링 급수로 근사한 값을 쓰는 것으로 충분하다

===== 정확한 값을 구하기 =====
  * 그냥 곱해서 구한다. O(n)
  * BigInteger환경에서 (곱셈 연산이 O(1)이 아닌 환경)에서 빠르게 구하는 알고리즘들이 많이 있다. 파이썬의 math.factorial은 [[http://www.luschny.de/math/factorial/binarysplitfact.html|Divide and conquer]] 방식으로 구현되어있다. 동작 설명은 사실 저 페이지보다도 그냥 [[https://hg.python.org/cpython/file/6fdbb81b4020/Modules/mathmodule.c#l1218|소스코드에 달린 docstring]]이 더 이해하기 쉽게 적혀있다. 
  * Multipoint evaluation 을 이용해서 $ O(\sqrt{n}log^{2}n) $ 에 구하는 방법이 있다고 하는데, 상당히 복잡하다. 
    * [[https://mono-cake.coffee/2020-04-13-Willson-Thm/]]와 [[http://www.secmem.org/blog/2019/06/16/Multipoint-evaluation/]] 를 참고

===== 팩토리얼 mod M 을 구하기 =====
  * 일단 트리비얼하게.. M≤n 이면 n!이 M으로 나눠지므로 나머지는 0이다.
  
==== M 이 n보다 큰 소수일 때 ====
  * 이게 가장 일반적으로 필요한 경우일테지만, 그냥 순수하게 1~n을 하나씩 곱하면서 M으로 나눈 나머지를 취하는 것을 반복하는 O(n)시간 알고리즘이 무난한 것 같다
    * n<1000 정도 범위까지는 그냥 math.factorial(n) % M 을 쓰는게 더 빠르다
  * 위에서 언급한 Multipoint evaluation을 이용하는 방법은 여전히 사용 가능하지만, 너무 복잡하다.
    * 괸련 문제는 [[https://www.acmicpc.net/problem/17467]], [[https://www.acmicpc.net/problem/17468]]


===== ?? =====

==== p^e | n! 인 e의 최댓값 구하기 ====
  * [[https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9#%EC%88%98%EB%A1%A0%EC%A0%81_%EC%84%B1%EC%A7%88|르장드르 공식]]을 사용한다. 공식은 간단하고 그냥 조금만 생각해봐도 유도가능  
    * $ v_{p}(n!)=\sum _{k=1}^{\infty }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor $
    * p^k가 n보다 커질때까지 계산하면 되니까. 시간복잡도는 $ O(log_{p}{n}) $

==== (n! / p^e) mod p 구하기 ====
  * [[https://cp-algorithms.com/algebra/factorial-modulo.html]]