[BOJ] 백준 1676번: 팩토리얼 0의 개수

www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

N! 은 1x2x3x4 x... N으로 곱하는 과정에서 10의 배수가 생길 때마다 0이 생깁니다.

다시 해석해보면 N!을 곱하는 전체 과정을 소인수 분해하여 2와 5의 개수를 찾으면 맨뒤에 오는 연속된 0의 개수를 알 수 있습니다.

좀 더 간단화시키면 2의 배수는 5의 배수보다 항상 많으므로 N! 를 소인수 분해하여 5의 개수를 찾으면 됩니다.

5, 10, 15, 20, .... 은 5를 1개 가지고 있습니다.

25, 50, 75, .... 는 5를 2개 가지고 있습니다. 

125, 250, 375, .... 는 5를 3개 가지고 있습니다.

즉 주어진 수 N을 5로 나눈 몫 + 25로 나눈 몫 + 125로 나눈 몫 ... 을 더하면 전체 5의 개수를 구할 수 있고 그것이 답이 됩니다.

#include <algorithm>
#include <cstdio>
#include <vector>
#include <iostream>
#include <memory.h>
#include <math.h>

using namespace std;
int p[101],n;
int gp(int x) {
	return (p[x] == x ? x : p[x] = gp(p[x]));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	// 5의 개수, 25의 개수, 125의 개수, 625의 개수, ...
	int ans = 0;
	int f = 5;
	while ( n >= f) {
		ans += n / f;
		f *= 5;
	}
	cout << ans;
}