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

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

1676번: 팩토리얼 0의 개수

[풀이]

팩토리얼을 일일이 구하면 어느 순간 기하급수적으로 커지기 때문에 한계가 있다. 

팩토리얼을 구하면서 10이 몇번 곱해지는 지를 구하면 된다.

1부터 N까지 for문을 돌리면서 각 수에 2와 5가 몇 개씩 포함되어 있는지 센다.

더 적은 개수가 2 * 5(10)의 개수이다.

ex)12 1, 2, 3, 4(2 * 2), 5, 6(2 * 3), 7, 8(2 * 2 * 2) , 9, 10(2 * 5), 11, 12(2 * 2 * 3) 2 개수 : 10개 5 개수 : 2개 2 * 5(10)의 개수 : 2개

그냥 5의 개수 구해도 될 듯하다

 

#include <iostream>
using namespace std;

int N;

long long getCnt(int num, int m) {
	long long cnt = 0;
	while (num%m == 0) {
		cnt++;
		num /= m;
	}
	return cnt;
}

void solution() {
	cin >> N;
	long long Mo2 = 0;//2의 배수 개수
	long long Mo5 = 0;//5의 배수 개수
	if (N == 0) {
		cout << 0 << endl;
		return;
	}
	//팩토리얼 안에 2 * 5가 몇 쌍 있는지 찾기
	for (int i = 1; i <= N; i++) {
		if (i % 2 == 0)
			Mo2 += getCnt(i, 2);
		if (i % 5 == 0)
			Mo5 += getCnt(i, 5);
	}
	//2와 5의 개수 중 더 적은 수가 2 * 5인 쌍의 수
	if (Mo2 < Mo5)
		cout << Mo2 << endl;
	else
		cout << Mo5 << endl;
}

int main() {
	solution();
	return 0;
}