GCD!

• k를 소인수분해 한 후에, 각 소인수별로 GCD(n!,k) 안에 얼마나 들어있는지를 구한 뒤 곱해주는 방식으로 풀면 된다
• p_i가 k 안에 얼마나 들어있는지는 소인수분해 과정에서 얻을수 있다.
• p_i가 n!안에 얼마나 들어있는지는 르장드르 공식으로 O(logn)에 구할수 있다
• 총 시간복잡도는 나이브하게 k를 소인수분해하는데에 O(sqrt(k))이 걸리고, 각 소인수들에 대해서 르장드르 공식을 적용하는데에 O(logn)이므로 총 O(sqrt(k) + {소인수의 개수}*logn) 이지만, 소인수의 개수는 상수로 볼수 있으므로 그냥 O(sqrt(k) + logn)이 된다.

"""Solution code for "BOJ 7806. GCD!".

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

Tags: [number theory]
"""

import sys
from teflib import psutils
from teflib import numtheory


def exponent_of_prime_in_factorial(n, p):
    """Compute largest power of a prime p that divides n!, in O(logn/logp)."""
    count = 0
    while n:
        n //= p
        count += n
    return count


@psutils.run_until_eof
def main():
    n, k = [int(x) for x in sys.stdin.readline().split()]
    factorization = numtheory.prime_factorization_small(k)

    answer = 1
    for p, e in factorization.items():
        e2 = exponent_of_prime_in_factorial(n, p)
        answer *= pow(p, min(e, e2))

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_factorization_small