[백준] 1676번: 팩토리얼 0의 개수

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

n!에서 r의 개수를 구하는 방법을 이용

 

예시) 10!, 2

10/2 = 5

5/2 = 2

2/2 = 1

 

10 9 8 7 6 5 4 3 2 1 
1       3    1     2    1

 

2가 여러번 곱해진 수는 곱한 횟수 만큼 나누어 떨어진다.

---

#include<string>
#include<iostream>

using namespace std;

int cnt(int n, int r) {
    int count = 0;
    while (n) {
        n /= r;
        count += n;
    }

    return count;
}

int main() {
    unsigned long int n;

    cin >> n;

    //2랑 5가 짝지어지는 횟수가 0의 개수
    int two = cnt(n, 2);
    int five = cnt(n, 5);

    if (two == 0 || five == 0) {
        cout << 0;
    }
    else if (two >= five) {
        cout << five;
    }
    else if (two <= five) {
        cout << two;
    }

    return 0;
}