ps:팩토리얼

팩토리얼 (Factorial)에서 넘어왔습니다.

목차

팩토리얼
토론

팩토리얼

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}) $

[코드] def exponent_of_prime_in_factorial(n, p) 펼치기

def exponent_of_prime_in_factorial(n: int, p: int):
    """Compute largest power of a prime p that divides factorial(n)."""
    count = 0
    while n:
        n //= p
        count += n
    return count

관련 문제
- 팩토리얼 0의 개수 팩토리얼 뒤의 0의 개수
- 시파르 팩토리얼 뒤의 0의 개수
- 교수가 된 현우 팩토리얼 뒤의 0의 개수
- GCD!

(n! / p^e) mod p 구하기

https://cp-algorithms.com/algebra/factorial-modulo.html

토론

실명:

이메일:

웹사이트:

댓글을 입력하세요:

인간임을 증명하기 위해 상자에 있는 모든 글자를 채워주세요. N J I X M 이 필드는 비어 있도록 유지하세요:

댓글 구독

ps/팩토리얼.txt · 마지막으로 수정됨: 2026/02/19 06:45 저자 teferi