====== 팩토리얼과 거듭제곱 ======

===== 풀이 =====
  * n!을 나누는 m의 최대 지수는 [[ps:tutorial:르장드르 공식]]을 활용해서 쉽게 구할 수 있다
  * 이것을 계산하는 과정에서 m의 소인수분해가 필요한데, 미리 sqrt(m)까지의 소수 목록을 계산해 둔 뒤에, 소수들에 대해서만 나누기를 하는 방식으로 소인수분해를 수행하면, 여러 테스트 케이스에 대해서도 케이스당 O(sqrt(m)/logm) 에 소인수분해가 가능하다.
  * 다 합치면 총 시간복잡도는 O(sqrt(m)) + O(t * (sqrt(m)/logm + logn))

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 3964. 팩토리얼과 거듭제곱".

- Problem link: https://www.acmicpc.net/problem/3964
- Solution link: http://www.teferi.net/ps/problems/boj/3964

Tags: [number theory]
"""

from teflib import io as tio
from teflib import numtheory
from teflib import primenum


@tio.run_n_times
def main():
    primenum.prime_list(10**6)

    n, k = tio.read_ints()
    print(numtheory.exponent_of_num_in_factorial(n, primenum.factorize(k)))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency
    * [[:ps:teflib:numtheory#exponent_of_num_in_factorial|teflib.numtheory.exponent_of_num_in_factorial]]
    * [[:ps:teflib:primenum#prime_list|teflib.primenum.prime_list]]


{{tag>BOJ ps:problems:boj:골드_2}}