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

===== 정확한 값을 구하기 =====
  * 그냥 곱해서 구한다. O(n)
  * BigInteger환경에서 (곱셈 연산이 O(1)이 아닌 환경)에서 빠르게 구하는 알고리즘들이 많이 있다. 파이썬의 math.factorial은 [[http://www.luschny.de/math/factorial/binarysplitfact.html|Divide and conquer]] 방식으로 구현되어있다. 동작 설명은 사실 저 페이지보다도 그냥 [[https://hg.python.org/cpython/file/6fdbb81b4020/Modules/mathmodule.c#l1218|소스코드에 달린 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의 최댓값 구하기 =====
  * {{myicon>s5}} k가 소수인 경우
    * [[https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9_(%EC%88%98%ED%95%99)#%EB%A5%B4%EC%9E%A5%EB%93%9C%EB%A5%B4_%EA%B3%B5%EC%8B%9D|르장드르 공식]]을 사용해서 쉽게 구할수 있다.
      * 공식 자체는 간단하고, 모르더라도 조금 생각해서 유도할 수 있다. 코드도 간단하다.
    * $ v_{p}(n!)=\sum _{k=1}^{\infty }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor $
      * p^k가 n보다 커질 때까지만 계산하면 되니까. 시간복잡도는 $ O(log_{p}{n}) $
    * **[코드] <fc #800080>def exponent_of_prime_in_factorial(n, p) </fc>** ++ 펼치기 |
<dkpr py>
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
</dkpr>
++
  * {{myicon>g4}} 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 중에서 가장 큰 값만 계산해도 된다
    * **[코드] <fc #800080>def exponent_of_num_in_factorial(n, k)</fc> ** ++ 펼치기 |
<dkpr py>
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

</dkpr>
++
    * n! 을 계산했을 때 뒤에 붙는 0의 개수는, 위에 식에서 k=10을 대입하면 된다. 10=2*5니까 그냥 $ v_5(n!) $ 를 구하면 충분하다
      * 마찬가지로 n!를 m진법으로 썼을때 뒤에 붙는 0의 개수는, k=m을 대입해서 계산하면 된다.
  * [[ps:tutorial:이항 계수]]를 팩토리얼들의 분수식으로 바꿔 쓰면, 이항 계수를 나누는 k의 최대 지수 역시 구할 수 있다.
  * 관련 문제
    * {{myicon>s5}} [[ps:problems:boj:1676]] [기본]: 팩토리얼 뒤의 0의 개수
    * {{myicon>s4}} [[ps:problems:boj:9693]] [기본]: 팩토리얼 뒤의 0의 개수
    * {{myicon>s3}} [[ps:problems:boj:3474]] [기본]: 팩토리얼 뒤의 0의 개수
    * {{myicon>s2}} [[ps:problems:boj:33532]] [기본]: 팩토리얼 뒤의 0의 개수
    * {{myicon>g4}} [[ps:problems:boj:4414]] [기본]: 팩토리얼이 k를 나누는지 여부
    * {{myicon>g3}} [[ps:problems:boj:7806]] [응용]: 팩토리얼과 k의 최대공약수
    * {{myicon>g2}} [[ps:problems:boj:3964]] [기본]: 팩토리얼을 나누는 k의 최대 지수 + 여러번의 소인수분해
    * {{myicon>g4}} [[ps:problems:boj:29469]] [기본]: 팩토리얼을 나누는 k의 최대 지수 
    * {{myicon>g2}} [[ps:problems:boj:7525]] [기본]: 팩토리얼을 나누는 k의 최대 지수 + 여러번의 소인수분해
    * {{myicon>g3}} [[ps:problems:boj:22693]] [기본]: 팩토리얼을 나누는 k의 최대 지수 

===== (n! / p^e) mod p 구하기 =====
  * [[https://cp-algorithms.com/algebra/factorial-modulo.html]]