BOJ 1676 - 팩토리얼 0의 개수

• N!을 구해서 오른쪽에서부터 consecutive한 0의 개수를 구하는 문제이다.

문제 풀이

• 0<=N<=500이기 때문에 팩토리얼을 직접 구해서 푸는 것은 overflow가 나기 때문에 \(N\)까지 수를 곱해가면서 0이 나오자마자 없애고 계산을 이어나가거나, 처음부터 powers of 5를 구해서 나눠주면 답이 나온다.

소스코드

#include<cstdio>
using namespace std;

int main()
{
	int n, res=0;
	scanf("%d", &n);
	for(int i=5;i<=n;i*=5)
		res+=n/i;
	printf("%d", res);
}

풀고나서

• 두 번 읽고나서야 문제를 이해했다.

• 처음 오버플로우나서 틀린 다음에 wolframalpha로 10!, 15!, 20!, 25!, 24!, 100!, 124!, 125!을 다 세보았다. 5의 거듭제곱수들로 나눈 몫들의 합이 정답이라는 것을 알아서 Accept는 했지만 왜 그런지 몰라서 질문게시판을 읽었다.
  팩토리얼을 소인수분해 했을때 2는 당연히 5보다 많기 때문에 5의 거듭제곱수만 신경써주면 되는 것이다. 5^2는 00, 5^3는 000이기 때문에 나눈 몫들을 모두 더해준다.