3474 교수가 된 현우

음.. 이 문제는 어떻게 해야할지 모르겠다.

 

입력이 10억이라 O(N)으로도 안 풀리고 10억개의 배열에 미리 저장할 용량도 안 된다. 

 

어떻게 풀지 떠오르는게 없는데... 

 

ㅗㅓ... 찾아보니 소인수분해로 계산하구나

 

숫자가 주어졌을 때 0몇 개 있는지 계산하려면 숫자에 10이 몇 번 곱해졌는지 확인하면 된다. 그럼 2의 개수와 5의 개수를 알면 됨

 

하지만 다들 이런 코드를 쓰는데 이해를 못하겠다

 

왜 제곱의 몫을 더하지???

 

 

오 신기하다 이렇게 계산 되는구나

 

개수가 제곱씩 줄어들어서 그럼

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

void    solve()
{
    int n;
    scanf("%d", &n);

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

    printf("%d\n", five);
}

int     main()
{
    int t;
    scanf("%d", &t);

    for (int i = 0; i < t; i++)
        solve();

    return 0;
}