팩토리얼과 거듭제곱

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

"""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()

• Dependency
  • teflib.numtheory.exponent_of_num_in_factorial
  • teflib.primenum.prime_list