[백준 1675] 팩토리얼 0의 개수, C++

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

1676번: 팩토리얼 0의 개수

 본 문제는 N! 에서 뒤어서부터 0이 아닐 때까지 0의 개수를 구하는 것이다. 팩토리얼에서 N이 13만 돼도 엄청 큰 숫자다 그렇기 때문에 직접 팩토리얼을 구한 다음 0의 개수를 셀 수 없다. 따라서, 뒤에 0이 나오기 위한 조건으로 구해야 한다. 어떤 수에 10이 곱해졌을 때, 뒷자리에 0이 추가된다. 그렇기 때문에 10이 곱해지는 개수를 구해야 하는데 10은 2 * 5이고 N! 에서 2의 개수보다 5의 개수가 무조건 적게 나오기 때문에 5 ~ N까지 반복하면서 X에 5가 몇 번 곱해져 있는지 확인하면 된다.

1. [5, N] 범위의 임의의 수 X를 5로 나누었을 때 나머지가 0일 경우
2. X를 5로 나누었을 때 나머지가 0이 아닐 때 까지 반복

#include <cstdio>
 
using namespace std;
 
int main() {
    int n, cnt = 0;
    scanf("%d", &n);
    for (int i = 5; i <= n; i++) {
        int k = i;
        while (true) {
            if (k % 5 == 0) {
                cnt += 1;
                k /= 5;
            }
            else break;
        }
    }
    printf("%d", cnt);
    return 0;
}