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

저번에 올린 팩토리얼 0의 개수처럼 비슷하게 풀면 됩니다.

차이점이 있다면, 팩토리얼에서는 5의 개수만 세었다면 이번에는 분모와 분자 각각 2, 5의 개수를 세서 차이를 계산해야 합니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	long long n, m;
	long long cnt2 = 0, cnt5 = 0;
	cin >> n >> m;

	for (long long i = 2; i <= n; i *= 2) {
		cnt2 += n / i;
	}
	for (long long i = 5; i <= n; i *= 5) {
		cnt5 += n / i;
	}
	for (long long i = 2; i <= n - m; i *= 2) {
		cnt2 -= (n - m) / i;
	}
	for (long long i = 5; i <= n - m; i *= 5) {
		cnt5 -= (n - m) / i;
	}
	for (long long i = 2; i <= m; i *= 2) {
		cnt2 -= m / i;
	}
	for (long long i = 5; i <= m; i *= 5) {
		cnt5 -= m / i;
	}


	cout << min(cnt2, cnt5);

	return 0;
}