[C/C++] 백준 #1676 팩토리얼 0의 개수(수학)

이번 문제는 팩토리얼을 계산했을 때, 뒤에서부터 연속된 0의 개수를 세는 것입니다.

 

팩토리얼은 1부터 n까지의 곱을 계산한 것인데요.  20 팩토리얼만 해도 2,432,902,008,176,640,000 값이 나와서 정수 계산으로는 힘듭니다.  물론 64비트 정수형을 사용하면 조금 더 계산할 수는 있습니다.  그런데 문제는 500까지의 숫자 범위를 가지고 있습니다.  500 팩토리얼은 \( 1.2 \times 10^{1134} \) 의 숫자로 굉장히 큰 숫자가 나오며, 파이썬이나 C#과 같이 기본적으로 Big Integer가 제공되는 언어가 아니라면, 실제 팩토리얼을 계산하기 힘듭니다.  n 팩토리얼 계산은 \(O(n)\) 알고리즘이라고 할 수 있지만, Big Integer 곱셈이 기본 연산이 아닌 관계로 더 오랜 시간이 걸립니다.

 

 

우리가 계산하고자 하는 계산은 뒤에 연속된 0의 개수입니다.  실제로 뒤에 연속된 0의 개수는 10의 멱승과 관련되죠.  예를 들어서 10 팩토리얼은 3,628,800 으로 뒤의 연속된 0의 개수는 2개입니다.  그 이야기는 10 팩토리얼은 100의 배수가 되죠.  100의 배수가 된다는 것은 \(2^2 \times 5^2\)의 배수가 된다는 것이죠.  1부터 10까지의 숫자중에서는 2의 배수가 5개가 있고, 5의 배수가 2개가 존재합니다.  2의 배수의 개수는 5의 배수의 개수보다 항상 많습니다.  더구나 4의 배수, 8의 배수까지 계산한다면, 2의 소인수는 총 8개가 나옵니다.  하지만 5의 소인수는 2개이므로 100의 배수가 되는 것이죠.

 

이것을 이용하면, n 팩토리얼이 10의 몇승의 배수가 되는지 계산할 수 있습니다.

 

\[ \sum_{i = 1}^{\infty} \lfloor \frac{n}{5^i} \rfloor \]

 

의 식으로 계산할 수 있습니다.  \(\infty\) 까지 쓰긴 했지만, \(5^i\) 값이 n보다 커지면, 더 이상 할 이유는 없습니다.

 

이것을 이용해서 프로그램한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//    baekjoon #1676 - Zero counting of factorial
//        - by Aubrey Choi
//        - created at 2019-06-07
//----------------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, c = 0;
    scanf("%d", &n);
    for(;n;c+=(n/=5));
    printf("%d\n", c);
}