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

팩토리얼

n이 조금만 커져도 정수형 범위를 넘어간다.
실용적인 경우에는 스털링 급수로 근사한 값을 쓰는 것으로 충분하다.
하지만 PS에서는 정확한 값을 필요로 하기 때문에 p로 나눈 나머지를 구하게 하는 경우가 대부분이다.

정확한 값을 구하기

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

k^e | n! 인 e의 최댓값 구하기

k가 소수인 경우
- 르장드르 공식을 사용해서 쉽게 구할수 있다.
  - 공식 자체는 간단하고, 모르더라도 조금 생각해서 유도할 수 있다. 코드도 간단하다.
- $ 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
```
k가 합성수인 경우
- 먼저 k를 소인수분해한 다음에, 각각 소인수에 대해서 최대 지수를 위의 방법으로 구한 뒤에, 최솟값을 구하면 된다
  - $ k = {p_1}^{e_1}\cdot{p_2}^{e_2} \cdot \ldots \cdot {p_m}^{e_m} $ 이라면 답은 다음과 같다
    - $ \min_i(\lfloor {\frac {v_{p_i}(n!)} {e_i}} \rfloor) $
    - 만약 e_i 가 모두 똑같다면, p_i 중에서 가장 큰 값만 계산해도 된다
- [코드] def exponent_of_num_in_factorial(n, k) 펼치기
```
from teflib.tutorial import prime_factorization

def exponent_of_num_in_factorial(n: int, k: int):
    """Compute largest power of a k that divides factorial(n)."""
    ret = INF
    for p, e in prime_factorization.trial_division(k).items():
        exp = exponent_of_prime_in_factorial(n, p)
        ret = min(ret, exp // e)
    return ret
```
- n! 을 계산했을 때 뒤에 붙는 0의 개수는, 위에 식에서 k=10을 대입하면 된다. 10=2*5니까 그냥 $ v_5(n!) $ 를 구하면 충분하다
  - 마찬가지로 n!를 m진법으로 썼을때 뒤에 붙는 0의 개수는, k=m을 대입해서 계산하면 된다.
이항 계수 (Binomial Coefficient)를 팩토리얼들의 분수식으로 바꿔 쓰면, 이항 계수를 나누는 k의 최대 지수 역시 구할 수 있다.
관련 문제
- 팩토리얼 0의 개수 [기본]: 팩토리얼 뒤의 0의 개수
- 시파르 [기본]: 팩토리얼 뒤의 0의 개수
- 교수가 된 현우 [기본]: 팩토리얼 뒤의 0의 개수
- Efficient Printing [기본]: 팩토리얼 뒤의 0의 개수
- Factovisors [기본]: 팩토리얼이 k를 나누는지 여부
- GCD! [응용]: 팩토리얼과 k의 최대공약수
- 팩토리얼과 거듭제곱 [기본]: 팩토리얼을 나누는 k의 최대 지수 + 여러번의 소인수분해
- 29469 [기본]: 팩토리얼을 나누는 k의 최대 지수
- 7525 [기본]: 팩토리얼을 나누는 k의 최대 지수 + 여러번의 소인수분해
- 22693 [기본]: 팩토리얼을 나누는 k의 최대 지수