BOJ [1676] 팩토리얼 0의 갯수

https://www.acmicpc.net/problem/1676

N!의 뒤에서부터 0 개수를 세는 문제.

N의 값은 0부터 500인데, 12!만 되어도 4억이 훌쩍 넘는다.

당연히 팩토리얼을 직접 구해서 풀 수 없다.

조금 달리 생각하여, 어떠한 값에 x10을 계산하면 뒤에 0이 하나씩 생긴다는 것에 주목했다.

N의 값을 받고 그 값을 소인수분해하여 (2 * 5) 한 세트당 1씩 증가시키면 된다.

2는 굉장히 많이 곱해질 것이기 때문에 결국 5의 개수만 세면 끝이다.

5! = 1 * 2 * 3 * 4 * 5 = 1 * 3 * 4 * (2 * 5) = 12 * 10 = 120
   ※ 1개

10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
       = 1 * 3 * 4 * 6 * 7 * 8 * 9 * (10 * 10)
   ※ 2개

15! = 1 * 2 * 3 * .... * 14 * 15
       = ... * 10 * 10 * 10 (15는 3 * 5이므로)
   ※ 3개

N값 범위 중 25는 5*5, 125는 5*5*5임에 유의하면 끝이다.

코드는 길지 않다.

#include <cstdio>

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d\n", (n/5) + (n/25) + (n/125));

	return 0;
}