백준 1676번 팩토리얼 0의 개수(C++)

solvd.ac 티어 : 실버5

문제 유형: 수학

문제 해결 방안 : 문제에서 최댓값인 500!은 너무 큰값이라서 일반적인 방법으로는 되지 않는다. 팩토리얼로 만든 값을 소인수분해하면 2가 항상 5보다 많고 10은 2와 5의 곱이다. 따라서 5가 몇번 곱해져 있는지를 세면 된다. 예를 들어 n이 15이면 5의 배수 5 10 15가 곱해져있다 15 = 5 * 3 즉, 15팩토리얼은 5가 곱해져 있는 수 3개가 곱해져 있다. 또한, 25는 5가 두번 곱해져있지만 5로 나누면 5가 1개 있는 수로 카운트 된다. 따라서 5 뿐만 아니라 25 125 625 ...으로도 나눠서 카운트 해줘야 한다.

문제 해결 소감 :무식하게 풀려고 해서 못 풀어서 인공지능에 물어봤다. 팩토리얼은 일반적인 반복문을 이용해서는 풀지 못한다는 것을 알고 있자.

#include <iostream>
int n = 0;
int cnt = 0;
int fac = 1;
int main()
{
    std::cin >> n;
    for (int i = 5; i < n; i *= 5)
    {
        cnt += n / i;
    }
    std::cout << cnt;
    return 0;
}