문제

문제 링크

해설

• 이런 종류의 문제는 항상 ‘정확히 해당 숫자’를 구할 필요가 없고, 오버플로 때문에 시간 내에 구할 수도 없습니다.
• 대략 10!를 직접 손으로 해보면 어떻게 풀 수 있을지 감이 잡힙니다.
  • 1, 2, 3, 4 팩토리얼은 0이 없습니다.
  • 5! = 5 × 4 × 3 × 2 × 1 = 120
    6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
    7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
    8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40320
    9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362880
    5, 6, 7, 8, 9 팩토리얼은 끝에 0이 1개 있습니다.
  • 여기까지 하면 대략적으로 감이 잡힙니다.
• 즉, ‘0’이 만들어지기 위해서는 2와 5가 곱해져야 하는데, 팩토리얼 과정에서 무수히 많은 2가 곱해집니다. 따라서 남은 재료는 ‘5’가 됩니다.
• 따라서 ‘0’은 5의 배수 때마다 한 개씩 늘어나게 됩니다. 어디 볼까요?
  • 10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3628800 으로 0이 2개죠?
  • 왜냐하면 10이 2 × 5이므로 위 식에서 5가 2개기 때문입니다.
• 마지막으로 주의해야 하는건 25, 125와 같이 5의 제곱인 경우 입니다.
  • 이건 5의 배수지만, 5가 2개, 3개가 있는 경우이므로 따로 카운팅을 해줘야 합니다.
• 위 내용들을 정리하면
• for (int i = 5; i <= N; i *= 5) answer += N / i; 한 줄로 표현할 수 있습니다.

코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;

        int answer = 0;
        for (int i = 5; i <= N; i *= 5) answer += N / i;

        cout << answer << '\n';
    }
    return 0;
}

소스코드 링크

결과