Processing math: 100%

−목차

팩토리얼
토론

팩토리얼

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

정확한 값을 구하기

그냥 곱해서 구한다. 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/ 를 참고

팩토리얼 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의 최댓값 구하기

르장드르 공식을 사용한다. 공식은 간단하고 그냥 조금만 생각해봐도 유도가능
- $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