c++ 백준 1676번 팩토리얼의 0의 개수

팩토리얼은 오버플로우가 생기기 쉽다. n이 500 까지이므로 팩토리얼을 계산한 후에 10으로 나누어 0의 개수를 세는 방법은 적절치 않다.

대체 방법으로 모든 수를 소인수 분해해서 5의 거듭제곱이 각각 몇 개 있는지 파악하는 방식이 있다.

#include <iostream>
using namespace std;

int countZeros(int n)
{
    int count = 0;
    for (int i = 5; n / i > 0; i *= 5)
    {
        count += n / i;
    }
    return count;
}

int main(int argc, char **argv)
{
    int N;
    cin >> N;

    int cnt = countZeros(N);
    cout << cnt;
    return 0;
}

 

 

10!을 생각해보자.

10* 9 * 8 * 7 ... * 2 * 1 이고, 10, 5, 2에서  2*5가 2쌍 있으므로 0의 개수는 2개이다.

 

 2의 인수가 5의 인수보다 많다. 그리고 5의 거듭제곱꼴로 0의 개수가 증가한다. $2^1 * 5^1$는 0의 개수가 1개이고, $2^2 * 5^2$는 2개이다. 즉 5의 거듭제곱의 개수가 0의 개수를 결정한다.

 

100!을 생각해보자.

100 * 99 * 98 * ... * 3 * 2 * 1 에서

 

5의 배수 20개( k = 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100  )는 각각 2*k를 만들 수 있다. (여기서 k는 5의 배수이다.)

e.g : (2*5), (2*10), (2*15) ... (2*100)

 

25의 배수 4개 (k= 25, 50, 75, 100 )는 각각  $(2*k)^2$를 만들 수 있고 이들은 0의 개수를 1개씩 더 추가한다. ( 여기서 k는 $5^2$의 배수이다.)

e.g : ($2^2*25$), ($2^2*50$), ($2^2*75$), ($2^2*100$)

 

즉, n!의 0의 개수는 n / 5 + n / 25 + n / 125 + ... 이다. (이때 n이 5의 거듭제곱보다 큰 경우까지만 계산해준다.)