[BOJ] 3964 팩토리얼과 거듭제곱 Python

 

K를 소인수분해한 뒤, 각각의 소인수가 몇번 곱해져있는지를 defaultdict를 통해서 저장한다...

 

인데, defaultdict을 안썼구나.

 

컨트롤이 어려웠던 부분은 처음 소인수분해 부분이었던 것 같다.

 

먼저, 2의 배수인지 판별한 뒤에, while에서 조금 테크닉을 사용했다.

 

int(sqrt ...) + 1까지 나눠봤을 때, 안 나눠진다면 그 친구는 소수라고 정의 하는것이 주효하게 사용되는 것 같다.

 

from collections import defaultdict
T = int(input())

for _ in range (0,T):
    N,K = map(int,input().split())
    #primeset을 통해 K를 나누는 소인수 집합을 구할 예정
    prime_set = {}
    if K % 2 == 0:
        cnt = 0
        while K % 2 == 0:
            cnt += 1
            K //= 2
        prime_set[2] = cnt
    num = 3
    while True:
        if K % num == 0:
            cnt = 0
            while K % num == 0:
                cnt += 1
                K //= num
            prime_set[num] = cnt
        else:
            num += 2
        if K == 1:
            break
        if num >= int(K ** (1/2)) +1:
            prime_set[K] = 1
            break

    prime_num = list(prime_set.keys())
    prime_cnt = list(prime_set.values())
    for i in range (0,len(prime_num)):
        #prime_num[i]가 소인수를 indicate, prime_num[i]에 대응하는 prime_cnt을 통해 총 몇번 나누어지는지 확인할 예정
        if i == 0:
            cnt,deg,n = 0,1,N
            while n > 1:
                cnt += n // (prime_num[i] ** deg)
                deg += 1
                if n < (prime_num[i] ** deg):
                    break
            ans = cnt//prime_cnt[i]
        else:
            cnt,deg,n = 0,1,N
            while n > 1:
                cnt += n // (prime_num[i] ** deg)
                deg += 1
                if n < (prime_num[i] ** deg):
                    break
            ans = min(ans, cnt//prime_cnt[i])
    print(ans)

 

 

 

 

와 진짜 많이 틀렸는데 어떻게든 통과해서 다행입니다 ......

 

즐거웠던 문제였습니다.

 

마지막 컨트롤이 조금 어려웠네요.