[백준 3474번] 교수가 된 현우 (C++)

문제링크 : https://www.acmicpc.net/problem/3474

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

int T, n, cnt;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> T;
    while(T--)
    {
        cnt = 0;
        cin >> n;

        for(int i=5; i<=n; i*=5) cnt += n/i;

        cout <<cnt << "\n";
    }


    return 0;
}

 

범위가 굉장히 크기에 단순 브루트포스를 통해서는 무조건 시간초과가 나는 문제이다.

0의 개수를 체크하려면 2*5의 경우를 세야하는데, 팩토리얼 구조상 2가 5보다 무조건 많을 수 밖에 없다.

따라서 5의 배수 개수만 세서 출력해주면 된다.