ps:팩토리얼
목차
팩토리얼
- n이 조금만 커져도 정수형 범위를 넘어간다.
- 실용적인 경우에는 스털링 급수로 근사한 값을 쓰는 것으로 충분하다
정확한 값을 구하기
- 그냥 곱해서 구한다. O(n)
- BigInteger환경에서 (곱셈 연산이 O(1)이 아닌 환경)에서 빠르게 구하는 알고리즘들이 많이 있다. 파이썬의 math.factorial은 Divide and conquer 방식으로 구현되어있다. 동작 설명은 사실 저 페이지보다도 그냥 소스코드에 달린 docstring이 더 이해하기 쉽게 적혀있다.
- Multipoint evaluation 을 이용해서 $ O(\sqrt{n}log^{2}n) $ 에 구하는 방법이 있다고 하는데, 상당히 복잡하다.
팩토리얼 mod M 을 구하기
- 일단 트리비얼하게.. M≤n 이면 n!이 M으로 나눠지므로 나머지는 0이다.
M 이 n보다 큰 소수일 때
- 이게 가장 일반적으로 필요한 경우일테지만, 그냥 순수하게 1~n을 하나씩 곱하면서 M으로 나눈 나머지를 취하는 것을 반복하는 O(n)시간 알고리즘이 무난한 것 같다
- n<1000 정도 범위까지는 그냥 math.factorial(n) % M 을 쓰는게 더 빠르다
- 위에서 언급한 Multipoint evaluation을 이용하는 방법은 여전히 사용 가능하지만, 너무 복잡하다.
??
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 구하기
ps/팩토리얼.txt · 마지막으로 수정됨: 2023/02/09 03:31 저자 teferi
토론