백준 7806번 파이썬 문제풀이(GCD!)

---

이 문제 코드 다 짜놓고 계속 틀리길래 엄한데 찾고 있었다.. 테케에서 입력횟수 제한을 안두면 알아서 try except로 EOFerror를 잡아줘야 한다. (참나... 이것때문에 엄한데서 오류를 찾고 2시간을 소비했다.... 죽어도 까먹지 말자.)

 

이 문제는 우선 K를 소인수 분해 해준다. 그렇다면 다음과 같이 소수 형태로 변한다.(2^3 * 3^5 * 7^2)... 그렇다면 이 소수들의 지수와 n!에서의 해당 소수의 지수 개수를 비교 해준다. 그 후 두개중 작은 개수를 최대공약수에 계속해서 곱해주면 된다. 예를들어) k의 소인수 분해 결과가 2^3 * 3^5 * 7^2 라고 하자. 하지만 n이 10이라서 10! 내에서는 2의 지수의 개수가 18개 3의 지수의 개수가 4개 7의 지수의개수가 1개이다. 따라서, 두개의 지수의 수를 비교해 보면 최대공약수는 2^3 * 3^4 * 7^1 이 되는 것이다.

 

# n!안의 해당 수가 몇개 들어있는지(해당 수의 지수가 몇인지)
def index_check_num(a):
    num = a
    count = 0
    while num <= n:
        count += n // num
        num *= a
    return count


try:
    while True:
        n, k = map(int, input().split())

        # 0!도 1이기 때문에 1로 바꾸어준다.
        if n == 0:
            n = 1

        arr = []  # 소인수 분해한 결과를 담을 변수
        x = k
        for i in range(2, k + 1):
            if i * i > k:
                break
            while x % i == 0:
                arr.append(i)
                x //= i
        if x != 1:
            arr.append(x)

        # 중복을 제거하기 위해 arr을 셋에 담아준다.
        # 2 2 2 3 3 과 같이 들어가있으면 2^3 * 3^2 와같기 때문에
        temp = set(arr)
        result = 1  # 결과를 출력하기 위한 변수

        # n!내에서 각각의 수가 몇개의 지수를 가지고 있는지 체크한 후에
        # 나의 개수와 n!내의 존재개수중 작은 수를 최대 공약수에 곱해준다.
        # 즉, n!내에 2가 6개 곱해져있고 k의 소인수 분해 결과가 2^3 이라면 2^3을 최대공약수에 곱해준다.
        for i in temp:
            if index_check_num(i) != 0:
                num = min(index_check_num(i), arr.count(i))
                result *= (i ** num)
        print(result)
except EOFError:
    exit()