팩토리얼 끝의 0의 개수는 어떻게 셀 수 있는가

1. 문제

 

1676번: 팩토리얼 0의 개수 (acmicpc.net)

1676번: 팩토리얼 0의 개수

 

2. 풀이

 

끝에서 0의 개수는 어떻게 세야할까

 

1000000은 뒤에 0이 6개이기 때문에, $10^{6}$이라고 바로 안다.

 

이처럼 끝에서 0의 개수가 n개이면, $10^{n}$이라고 바로 알고 있다

 

다른 수를 예로 들어보면 376129000은 $376129*10^{3}$

 

따라서 어떤 수에서 끝의 0의 개수는... 소인수 분해해서 10이 몇개나 있는지 계산하면 될 것이다.

 

여기서 10은 2와 5의 곱이므로, 소인수분해해서 2와 5의 개수가 몇개나 있는지 계산하면 될 것이다

 

from sys import stdin

def factorization(n):
    
    target = n
    
    #소인수의 개수
    cnt = [0]*(n+1)

    while n > 1:
        
        #소수 판정
        for i in range(2,n+1):
            
            prime = True
            
            for j in range(2,int(i**(1/2))+1):
                
                if i % j == 0:
                    
                    prime = False
                    
                    break
            
            #i가 소수라면...
            if prime:
                
                #n이 소수 i로 나누어 떨어지면..
                if n % i == 0:
                    
                    #나누어보고
                    n = n//i
                    
                    #해당 i의 개수를 1 증가
                    cnt[i] += 1

                    break
    
    #n이 5이상이라면, 2의 개수와 5의 개수를 모두 return
    if target >= 5:
    
        return cnt[2],cnt[5]
    
    #n이 5보다 작으면 5의 개수는 0개이다
    else:
        
        return cnt[2],0

 

예전에 푼건데 지금 보니까 소인수분해 왜이렇게 복잡하게 했냐..

 

아무튼 n을 소인수분해해서, 소인수중 2와 5의 개수를 return해준다

 

이제 n을 입력받고, n!을 계산할건데...

 

n!을 계산하고 factorization하는게 아니라, n!은 2부터 n까지의 곱이니까, 2부터 n까지 각각 factorization해서

 

2와 5의 개수를 찾은 다음에 지수법칙에 의해 이들을 곱하면 될거니까

 

그랬을때, $2^{a}*5^{b}$가 될건데, 이를 10의 거듭제곱으로 바꿀려면?

 

$10^{min(a,b)} * 2^{c} * 5^{d}$로 될것이다.

 

따라서, 2와 5의 개수의 최솟값이 답이 된다

 

n = int(stdin.readline())

if n <= 1:
    
    print(0)

else:

    ans2 = 0
    ans5 = 0

    for i in range(2,n+1):
        
        a,b = factorization(i)

        ans2 += a
        ans5 += b

    print(min(ans2,ans5))

 

 

3. 최적화하기1

 

일단 소인수분해가 조금 더러운것?같아서 아쉽다...

 

내가 알고있는 기본 소인수분해 코드로 조금 바꿔보자고

 

from sys import stdin

def factorization(n):
    
    p = 2

    cnt = [0]*(n+1)

    while p*p <= n:

        while n % p == 0:
            
            n = n//p

            cnt[p] += 1
        
        p += 1
    
    if n > 1:
        
        cnt[n] += 1
    
    return cnt

n = int(stdin.readline())

if n <= 1:
    
    print(0)

else:
    
    ans2 = 0
    ans5 = 0

    for i in range(2,n+1):
        
        cnt = factorization(i)

        if i >= 5:
            
            ans2 += cnt[2]
            ans5 += cnt[5]
        
        else:
            
            ans2 += cnt[2]
    
    print(min(ans2,ans5))

 

4. 최적화하기2

 

더욱 문제를 깊게 이해해보면.. 아주 쉽게 해결할 수 있다

 

예를 들어 30!을 생각해보면.. 1부터 30까지의 곱이다.

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

 

그러면 앞에서 2의 개수와 5의 개수의 최솟값이 뒤에서부터 0의 개수라고 했는데..

 

1부터 30중에서 2를 인수로 가지는 수는... 30/2 = 15개

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

 

그런데 4는 2를 인수로 더 가지고 있으므로... 30/4 = 7개

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

 

마찬가지로 8은 2를 인수로 더 가지고 있으므로.. 30/8 = 3개

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

 

마찬가지로 16은 2를 인수로 더 가지고 있으므로... 30/16 = 1개

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

 

그러므로, 30!의 인수 2의 개수는.. 30/2 + 30/4 + 30/8 + 30/16 = 15+7+3+1 = 26개

 

마찬가지 방법으로 인수 5의 개수를 세보자

 

30/5 = 6개일것이다.

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

 

그런데 25는 5를 인수로 1개 더 가지므로... 30/25 = 1개가 더 있다

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

 

 

따라서 30!이 인수로 가지는 5의 개수는 30/5 + 30/25 = 6+1 = 7개이다.

 

따라서, 2의 인수는 26개 5의 인수는 7개이므로... 이들의 최솟값인 7이 30! 뒤에 붙은 0의 개수이다.

 

from sys import stdin

n = int(stdin.readline())

ans2 = 0
ans5 = 0

i = 1

while 1:
    
    x = n//(2**i)

    if x == 0:
        
        break

    ans2 += x

    i += 1

j = 1

while 1:
    
    x = n//(5**j)

    if x == 0:
        
        break
    
    ans5 += x

    j += 1

print(min(ans2,ans5))

 

 

5. 최적화하기3

 

더욱 깊게 통찰하면... 5의 인수의 개수는 2의 인수의 개수보다 항상 더 작다는 사실이다.

 

n!이 1부터 n까지의 곱인데, 1부터 n까지 나열해보면... 너무 명백하다.

 

2가 5보다 작기때문에 1부터 n까지에서 2가 더 많이 나타나는 것은 자명하다

 

from sys import stdin

n = int(stdin.readline())

answer = 0

j = 1

while 1:
    
    x = n//(5**j)

    if x == 0:
        
        break
    
    answer += x

    j += 1

print(answer)

 

 

6. 문제2

 

11687번: 팩토리얼 0의 개수 (acmicpc.net)

11687번: 팩토리얼 0의 개수

 

7. 풀이

 

위의 원리를 이해하고 있다면, n!의 뒤의 0의 개수는 쉽게 구할 수 있을 것이고...

 

이분탐색으로 n의 최솟값을 쉽게 찾을 수 있겠다

 

start부터 end까지 잡고, mid에 대해, mid!의 0의 개수를 구한 다음에, target = m과 비교하여...

 

target이상이라면... 그 이후는 점점 커지므로 end = mid로 옮겨서 작은쪽을 보도록 하고

 

target보다 적다면... mid이전에는 답이 없으므로, start = mid+1로 옮겨서 큰쪽을 탐색한다.

 

from sys import stdin

def factorial_zero(n):
    
    answer = 0

    i = 1

    while 1:
        
        x = n//(5**i)

        if x == 0:
            
            break
        
        else:

            answer += x
            i += 1
    
    return answer

def binary_search(target,start,end):
    
    while start < end:
        
        mid = start + (end - start)//2

        if factorial_zero(mid) >= target:
            
            end = mid
        
        else:
            
            start = mid + 1
    
    return end
          
m = int(stdin.readline())

answer = binary_search(m,1,1000000001)

if factorial_zero(answer) != m:
    
    print(-1)

else:
    
    print(answer)

 

 

 

[BaekJoon][1676] 팩토리얼 0의 개수 - :: ADVANCE :: (tistory.com)

[BaekJoon][1676] 팩토리얼 0의 개수

 

 

팩토리얼의 끝 0의 개수 구하기 - Parkito's on the way (shoark7.github.io)

팩토리얼의 끝 0의 개수 구하기