[BOJ/1676] 팩토리얼 0의 개수

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

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

 

사용 알고리즘

- 

 

풀이

- 끝자리가 0이 되려면 2와 5가 필요

- 따라서 0이 몇 개인지 알아내려면, N!를 소인수 분해하여 2와 5의 개수중 작은 수의 개수가 0의 개수

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/1676.cpp

#include <cstdio>
 
int main(void) {
    int fivesCount = 0, twosCount = 0;
    int n; for (scanf("%d", &n); n--;) {
        int num = n + 1;
        while (num % 5 == 0) {
            num /= 5;
            ++fivesCount;
        }
        while (num % 2 == 0) {
            num /= 2;
            ++twosCount;
        }
    }
    printf("%d\n", (fivesCount < twosCount) ? fivesCount : twosCount);
    return 0;
}