테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== GCD! ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency:  [[:ps:teflib:numtheory#prime_factorization_small|teflib.numtheory.prime_factorization_small]]

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