[백준] 알고리즘 C++ 2004번 - 조합 0의 개수문제

문제

https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	long long n, m;
	cin >> n >> m;
	long long two = 0, five = 0;
	for (long long i = 2; i <= n; i *= 2) {
		two += n / i;
	}
	for (long long i = 5; i <= n; i *= 5) {
		five += n / i;
	}
	for (long long i = 2; i <= m; i *= 2) {
		two -= m / i;
	}
	for (long long i = 5; i <= m; i *= 5) {
		five -= m / i;
	}
	for (long long i = 2; i <= n - m; i *= 2) {
		two -= (n - m) / i;
	}
	for (long long i = 5; i <= n - m; i *= 5) {
		five -= (n - m) / i;
	}
	cout << min(two, five) << "\n";
}

해설

이전의 팩토리얼 문제에서는 5의 개수가 무조건 작았지만 현재 조합에서의 식을보면 어떤게 더 작을지 모르는 상황입니다.

즉 2와5가 포함된 개수를 전부 계산하여 비교한후 개수를 출력해줘야 합니다.