[2004] 조합 0의 개수

---

 

조합은 알다시피 nCr=(n!)/[{(n-m)!}(m!)] 으로 구할 수 있다

팩토리얼 0의 개수를 구하는 방법을 알았으니, f(n) - f(n-m) - f(m)을 하면 조합 0의 개수가 나올 줄 알았다

0의 개수는 결국 10의 개수인건데, 분모로부터 분자에 있는 10의 개수를 빼야 최종 10의 개수가 나오기 때문이다

 

그래서 이 문제를 참고했는데

https://kmyobin.tistory.com/56

[1676] 팩토리얼 0의 개수

이거대로 했더니 틀렸다

5의 x제곱의 개수를 기준으로 0의 개수를 계산한 것이 문제였다

 

여기서는 반례가 등장한다

5C1인 경우 2의 배수로 구한 0의 개수가 답이 된다

그러므로 2의 x제곱의 개수, 5의 x제곱의 개수로 구한 0의 개수를 비교하여 더 작은 값을 선택해야 한다

여기서는 2의 x제곱의 개수가 더 작을 수도 있다는 생각을 놓쳐서는 안된다

 

그러므로 이를 참고하여 문제를 풀었고, 완성된 코드는 아래와 같다

참고로 5의 x제곱의 수, 2의 x제곱의 수의 limit를 생각하여 integer overflow가 발생되지 않게 하였다

#include <iostream>
#include <cmath>
using namespace std;

int n, m;

int two(int x) {
	int r = 0;
	for (int i = 1; i <= 30; i++) {
		r += x / pow(2, i);
	}
	return r;
}

int five(int x) {
	int r = 0;
	for (int i = 1; i <= 13; i++) {
		r += x / pow(5, i);
	}
	return r;
}

int main() {
	cin >> n >> m;
	// 5^13 = 1,220,703,125
	// 2^30 = 1,073,741,824

	int R = two(n) - two(n - m) - two(m);
	int S = five(n) - five(n - m) - five(m);

	int F = min(R, S);
	printf("%d", F);

}