1676번 팩토리얼 0의 개수

팩토리얼 0의 개수

풀이

를 직접 계산하기에는 그 수가 너무 크므로 다른 방법을 생각해야 합니다.

어떤 수의 뒤에서부터 이어지는 의 개수는 그 수를 으로 몇 번 나눌 수 있느냐와 같습니다.

예를 들어 은 소인수분해 했을 때 으로 으로 최대 두 번 나눌 수 있습니다.

이므로 와 의 지수 중 최댓값이 됩니다.

팩토리얼에서는 의 배수는 번마다 나오는 데 반해 의 배수는 번에 한 번 나오므로 어떤 팩토리얼이든 의 지수가 의 지수보다 큽니다.

따라서 부터 까지 의 배수를 검사하여 의 지수를 구하면 답이 됩니다.

코드

def main():
    N = int(input())
 
    exp = 0
    for i in range(1, N + 1):
        while i % 5 == 0:
            i //= 5
            exp += 1
    
    print(exp)
 
 
main()