조합 0의 개수 (feat. 백준, 2004번)

조합 0의 개수
https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2004
#include <iostream>
#include <cmath>
using namespace std;
int two(register int n) {
	register int value = 0;
	for (register long long i = 2; i <= n; i *= 2)
		value += n / i;
	return value;
}
int five(register int n) {
	register int value = 0;
	for (register long long i = 5; i <= n; i *= 5)
		value += n / i;
	return value;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M;
	cin >> N >> M;
	cout << min(five(N) - five(N - M) - five(M), two(N) - two(N - M) - two(M));
	return 0;
}
// *&)*@*

위 문제는 이전 "팩토리얼 0의 개수" 의 응용버전입니다. 따라서 아래 문제를 먼저 풀어보시길 권장합니다.

팩토리얼 0의 개수 (feat. 백준, 1676번)

---

• 10, 20, 30, ..., 100 은 2와 5로 나누어집니다. 즉, 우측에 0이 오기 위해서는 2와 5로 나누어져야 한다는 말이 됩니다.
• 5C1은 5! / 1! * 4! 입니다.
• 5는 5로 나누었을때 1개 입니다. 1은 5로 나누었을때 0개 입니다. 4는 5로 나누었을때 0개 입니다. 따라서 1 - 0 - 0 = 1 입니다.
• 5는 2로 나누었을때 2개 입니다. 또한 2의 제곱인 4보다 크거나 같으므로 5는 4로 나누었을때 1개 입니다. 따라서 3개 입니다.
• 1은 2로 나누었을때 0개 입니다. 4는 2로 나누었을때 2개 입니다. 또한 2의 제곱인 4보다 크거나 같으므로 4는 4로 나누었을때 1개 입니다. 따라서 3개 입니다.
• 따라서 3 - 0 - 3 = 0 입니다.
• 2로 나누었을때의 결과와 5로 나누었을때의 결과 중 최소값을 찾습니다. 따라서 min(1, 0) = 0 입니다.