팩토리얼을 계산하지 않고도 소인수분해하는 기본기

1. 문제

 

15996번: 팩토리얼 나누기 (acmicpc.net)

15996번: 팩토리얼 나누기

 

2. 풀이

 

n의 범위가 $2^{31} = 2147483648$까지로 이것의 팩토리얼을 계산하면... 상상하기도 힘든 숫자가 나올거는 뻔하니

 

계산하지 않고 $A^{k}$로 나눠보라는 말일텐데 어떻게 가능할까

 

예를 들어 생각하면 생각보다 간단한 문제다

 

5! = 5*4*3*2*1인데 $2^{k}$로 나눈 나머지가 0이 되는 최대의 k는 어떻게 찾을까

 

만약 k = 0이면 당연히 5!은 1로 나누어 떨어진다

 

k = 1이라면, 2로 나눌 수 있느냐인데.. 5! = 5*4*3*2*1로 2를 인수로 가지니 나누어 떨어진다

 

k = 2이면 $2^{2}$으로 나눌 수 있느냐인데, 5! = 5*4*3*2*1이 2를 인수로 2번 가지는지 확인해보면 될 것이다

 

실제로 5!은 2를 3개나 인수로 가지고 있다. 그러니까 $2^{2}$으로도 나누어 떨어진다

 

마찬가지로 k = 3이면 $2^{3}$으로 나누어 떨어지는지 체크해야하는데, 2를 3개 가지고 있으니 나누어 떨어진다.

 

즉, 5!이 2를 3개 가지고 있기때문에 k의 최댓값은 3이다.

 

그러면 우리가 체크해야할것은 n!이 A를 몇개나 가지고 있는지 체크하면 된다

 

어떻게 가능할까?

 

가장 쉬운 방법은 n! = n*(n-1)*...*1이니까 1부터 n까지 모두 순회해서, A로 나누어 떨어지는지 체크하는 것이다.

 

각각이 A로 몇번이나 나누어 떨어지는지 체크한다면 n!이 A를 몇개나 인수로 가지는지 알 수 있을 것

 

n,a = map(int,input().split())

answer = 0

for i in range(1,n+1):
    
    count = 0

    while i % a == 0:

        count += 1

        i //= a

    answer += count

print(answer)

 

하지만 N의 최댓값이 2147483648으로 21억인데 1초안에 가능할리가 없다

 

O(N)보다 더 빠른 방법이 필요하다는 소리인데

 

1부터 N까지 A가 몇개나 존재하는지 체크한다는 것은 1부터 N까지 A로 나누어 떨어지는 수가 몇개나 있는지 체크하는 것과 같다.

 

이는 다시 말하면 1부터 N까지에서 A를 약수로 가지는 수가 몇개나 있는지 체크하는 것과 같다.

 

그런데 A를 약수로 가지는 수를 세는 것보다 A의 배수가 몇개나 있는지 세는 것이 더 쉽다는 것을 배웠다

 

N//A로 O(1)만에 셀 수 있다

 

그런데 N//A개만 있을까?

 

당장 5! = 5*4*3*2*1만 해도 2가 몇개나 있는지 체크해보면 3개 있는데 5//2 = 2이다.

 

5//2가 세는 것은 4와 2인데 4는 2를 2개나 가지고 있다

 

4는 2^{2}과 같다.

 

4는 2로 2번 나누어 떨어지기 때문에, A의 거듭제곱이 몇개인지도 세줘야한다.

 

구체적으로 N!이 가지고 있는 A의 개수는... N//A + N//A^{2} + N//A^{3} + ...

 

$$\sum_{k = 1} \left \lfloor \frac{N}{A^{k}} \right \rfloor$$

 

n,a = map(int,input().split())

answer = 0

k = 1

while 1:
    
    x = n//(a**k)

    if x == 0:
        
        break

    answer += x
    
    k += 1

print(answer)