CSES 1. Trailing Zeros (1618)

출처: https://cses.fi/problemset/task/1618

---

문제 설명

Your task is to calculate the number of trailing zeros in the factorial n!n!.

For example, 20!=2432902008176640000 and it has 4 trailing zeros.

입력

The only input line has an integer n.

출력 양식

Print the number of trailing zeros in n!.

입력 예

20

출력 예

4

제약조건

1 <= n <= 10^9

---

문제 풀이

팩토리얼에서 뒤에 나오는 0의 갯수는 N보다 작은 수중에서 곱해지는 5나 5의 거듭제곱수들이 몇번인가와 같다. 그래서, 5로 계속 나누면서 나오는 수들을 누적해서 출력한다. 엄밀하게는 2와 2의 거듭제곱수들의 빈도수와 비교해야 한다.

프로그램 내용

#define MAX_N 1000000000

int main()
{
    int N;
    cin >> N; 

    /// count number of 5 less than N
    int count_5=0;
    int div=1;
    long base = N;

    while(div != 0)
        div = base / 5;
        count_5 += div;
        base = div;

	cout << count_5 << endl;

 

Introductory problems ( link )