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

 

문제 URL:

www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

다음 문제는 N! 의 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제로

(=숫자 가운데에 존재하는 0은 신경 쓰지 않음, 끝자리의 연속되는 0의 개수를 구해야 함)

팩토리얼 값을 직접 구하는 문제가 아니라 2와 5의 개수를 이용하여 푸는 문제였다.

 

2와 5를 곱해야 10이 나오게 되므로 결과적으로 1부터 n까지 수를 각각 소인수분해했을 때 나오게 되는

모든 2와 5가 몇 쌍을 이루는지 개수를 구하면 되는데,

여기서 당연히 5의 개수가 더 적으므로 결국 5의 개수가 구해야 하는 0의 개수이다.

 

여기서 주의할 점은 25, 50, 125 같은 수들은 인수로 5를 하나만 가지고 있는 것이 아니기 때문에 개수를 더 세어주어야 한다.

---

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int count=0, x=5;
    while(n>=x)
    {
        count = count + n/x;
        x *= 5;
    }
    
    cout << count;
}