[C++] [CSES] Trailing Zeros (Introductory Problems)

CSES의 열번째 문제입니다.

팩토리얼의 뒤에 0이 몇 개 있는지 알아내야 합니다.

예를 들어 10!은 3628800로 뒤에 0이 2개 있습니다.

 

Task

Your task is to calculate the number of trailing zeros in the factorial n!.
For example, 20!=2432902008176640000 and it has 44 trailing zeros.

Input

The only input line has an integer n.

Output

Print the number of trailing zeros in n!.

Constraints

• 1≤n≤1e9

Example

Input:
20

Output:
4

 

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n;
int main(){
    cin >> n;
    ll ret = 0, fiv = 5;
    while (n >= fiv){
        ret += n / fiv;
        fiv *= 5;
    }
    cout << ret;
}

생각해야 하는 것

• 뒤에 0이 생긴다는 것은 (~~~ * 10) 의 형태로 나타나주어야 한다는 것을 말합니다.
• 10은 2 * 5로 나타낼 수 있습니다.
• 팩토리얼에서는 두번 중 한번 꼴로 2가 등장하기 때문에 우리가 구해야 할 것은 "팩토리얼에서 5가 몇번 사용되었는가" 입니다.
• 예를 들어 30!은 5의 배수가 5, 10, 15, 20, 25, 30으로 6개 있습니다. 30!을 소인수분해한다면 (~~ * 2^n * 5^6) 으로 나타낼 수 있습니다. 여기서 n은 무조건 6을 초과합니다.
• fiv라는 변수가 5부터 5씩 곱해가면서 몫을 더해준다면 팩토리얼에서 5의 등장 횟수를 쉽게 알 수 있습니다.