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

문제

1676번: 팩토리얼 0의 개수

n이 주어지면 n!의 뒤에서 부터 0이 아닌 수가 나올 때까지 0의 개수를 세는 문제입니다.

우리가 숫자 뒤에 0이 붙게 될려면 숫자에서 10을 곱해주면 됩니다.

 

즉 숫자에서 10이 몇번 곱해있는지 확인하면 뒤에 0이 몇번 붙었는지 알 수 있습니다.

10을 소인수분해 하면 2 * 5가 나옵니다.

결국 1부터 n까지 2와 5의 약수의 개수를 세고 작은 수를 출력하면 됩니다.

 

모든 수는 5의 약수가 훨씬 적으므로 우리는 1부터 n까지 돌아가면서 5의 약수를 구하면 됩니다.

만약 i가 5의 거듭제곱 꼴(ex : 25, 125 등등) 이면 단순히 (i % 5 ==0) 이러한 코드를 실행하면 cnt가 1밖에

안늘어 나므로

if (i % 125 == 0)
	cnt += 3;
else if (i % 25 == 0)
	cnt += 2;
else if (i % 5 == 0)
	cnt++;

이러한 코드를 작성해 모두 세우주기로 합니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
 
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 125 == 0)
            cnt += 3;
        else if (i % 25 == 0)
            cnt += 2;
        else if (i % 5 == 0)
            cnt++;
    }
    cout << cnt;
 
    return 0;
}