팩토리얼

정확한 값을 구하기

그냥 곱해서 구한다. O(n)
BigInteger환경에서 (곱셈 연산이 O(1)이 아닌 환경)에서 빠르게 구하는 알고리즘들이 많이 있다. 파이썬의 math.factorial은 Divide and conquer 방식으로 구현되어있다. 동작 설명은 사실 저 페이지보다도 그냥 소스코드에 달린 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/ 를 참고

이게 가장 일반적으로 필요한 경우일테지만, 그냥 순수하게 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

르장드르 공식을 사용한다. 공식은 간단하고 그냥 조금만 생각해봐도 유도가능
- $ v_{p}(n!)=\sum _{k=1}^{\infty }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor $
- p^k가 n보다 커질때까지 계산하면 되니까. 시간복잡도는 $ O(log_{p}{n}) $