백준 2004 : 조합 0의 개수

★★☆☆☆

직전에 풀었던 팩토리얼 0의 개수를 활용하면 어렵지 않다.

<나의 풀이>

맨처음에는 우선..25C12를 직접 구해보았다...ㅋㅋㅋ
조합의 기본식을 적어보았더니, 조합이 결국 팩토리얼들의 연산으로 이루어진다는 것을 알았다.
팩토리얼 0의 개수 문제의 알고리즘을 활용하기로 했다.

분모와 분자의 팩토리얼 값들이 서로 약분되면서, 최종 숫자가 나오게 되기 때문에
약분되는 0 값들은, 5의 개수들의 차가 될 것이기 때문에 분자 팩토리얼의 5의개수-분모 팩토리얼의 5의 개수 연산을 해주자는 결론이 나왔다.

그런데 여기서 팩토리얼 문제와의 차이점이 드러났다.
팩토리얼 문제에서는 5의 개수가 무조건 2보다 더 적기때문에 5의 개수만을 구해주었지만,
조합의 경우 분모분자가 약분되는 과정에서 2의 개수가 더 적어질 수 있었다.
따라서, 직접 5의 개수와 2의 개수를 모두 구해서 더 적은 값을 출력해주게되었다.

#include <iostream>
using namespace std;

int min(long long x, long long  y) { //작은값 return
	if(x >= y) return y;
	else return x;
}

long long getfive(long long n) { //5의 개수
	long long r = 5;
	long long ret=0;
	while (r <= n) {
		ret += n / r;
		r = r * 5;
	}
	//cout << "[five] n :: " << n << ", ret :: " << ret << "\n";
	return ret;
}
long long gettwo(long long n) { //2의 개수
	long long r = 2;
	long long ret = 0;
	while (r <= n) {
		ret += n / r;
		r = r * 2;
	}
	//cout << "[two] n :: " << n << ", ret :: " << ret << "\n";
	return ret;
}

int main() {
	long long m, n;
	cin >> n;
	cin >> m;

	long long ret = 0;
	ret = min(getfive(n) - getfive(n - m)- getfive(m), gettwo(n) - gettwo(n - m) - gettwo(m)); 
    //5의 개수와 2의 개수 중 더 적은 값을 출력하기
	cout << ret << "\n";
	return 0;
}