Factovisors

• 르장드르 공식 (Legendre's formula)을 활용하면, n!을 나누는 m의 최대 지수를 구할 수 있다. 이 값이 0이면 m이 n!을 나누지 못하는 것이고, 1 이상이면 나눌 수 있는 것.
• 이것을 계산하는 과정에서 m의 소인수분해가 필요한데, 미리 sqrt(m)까지의 소수 목록을 계산해 둔 뒤에, 소수들에 대해서만 나누기를 하는 방식으로 소인수분해를 수행하면, 여러 테스트 케이스에 대해서도 케이스당 O(sqrt(m)/logm) 에 소인수분해가 가능하다.
• 다 합치면 총 시간복잡도는 O(sqrt(m)) + O(t * (sqrt(m)/logm + logn))
• 매우 괴상한 에지 케이스가 있다. m이 0일 경우에는 '나누지 못한다'를 출력해야 한다
  • m이 0일때 '나눌수 없다'고 출력하는게 사실 맞는것인지도 의심이 간다. undefined behavior 인데, 저렇게 표현하는게 맞는 거긴 한가?

"""Solution code for "BOJ 4414. Factovisors".

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

Tags: [number theory]
"""

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


@tio.run_until_eof
def main():
    primenum.prime_list(2**16)

    n, m = tio.read_ints()

    if m == 0:
        print(f'{m} does not divide {n}!')
        return

    e = numtheory.exponent_of_num_in_factorial(n, primenum.factorize(m))
    if e == 0:
        print(f'{m} does not divide {n}!')
    else:
        print(f'{m} divides {n}!')


if __name__ == '__main__':
    main()

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