[C++/백준 2004번] 조합 0의 개수

 

 

 

조합 공식과 정수론을 이용해 해결하는 문제.

 

조합 공식은 nCr n! / (n-r!) r! 이다. 

 

그리고 10을 구성하는 소인수는 2 x 5 인데, 2와 5 소인수 중 개수가 작은 것이 0의 개수가 될 것이다. 

 

팩토리얼의 소인수를 구하는 방법은 

https://blog.naver.com/shalska1234/50087466089

계승(factorial, !)의 소인수분해!

 

이 블로그 게시글을 참고했다. 

 

100! -> 100 / 2, 100 / 4, 100/ 8 , 100 / 16  , 100 / 32 , 100 / 64 의 값을 모두 더하면 2의 소인수 개수가 된다.

 

따라서 n! 의 2 소인수 개수 - (n!-r!) 의 2 소인수 개수 - r ! 의 2 소인수 개수 를 해주면 해당 조합의 2 소인수 개수가 나온다. 

5도 똑같은 방식으로 적용하여 계산하면 문제를 해결할 수 있다.

 

 

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

long long d2(long long input)
{
	long long cnt = 0;
	for (long long i = 1; i <= input; i *= 2)
	{
		if (i > input) break;
		cnt += input / i;
	}
	return cnt;
	
}

long long d5(long long input)
{
	long long cnt = 0;
	for (long long  i = 1; i <= input; i *= 5)
	{
		if (i > input) break;
		cnt += input / i;
	}
	return cnt;
}


int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	long long n, m;
	long long count = 0;
	cin >> n >> m;


	count = min(d5(n) - d5(m) - d5(n - m), d2(n) - d2(m) - d2(n - m));
	


	cout << count;
}