사용자 도구

사이트 도구


ps:팩토리얼

팩토리얼

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

정확한 값을 구하기

팩토리얼 mod M 을 구하기

  • 일단 트리비얼하게.. M≤n 이면 n!이 M으로 나눠지므로 나머지는 0이다.

M 이 n보다 큰 소수일 때

  • 이게 가장 일반적으로 필요한 경우일테지만, 그냥 순수하게 1~n을 하나씩 곱하면서 M으로 나눈 나머지를 취하는 것을 반복하는 O(n)시간 알고리즘이 무난한 것 같다
  • 위에서 언급한 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 구하기

토론

댓글을 입력하세요:
M A V H E
 
ps/팩토리얼.txt · 마지막으로 수정됨: 2021/01/24 14:20 저자 teferi