조합 0의 개수 (백준 2004)

안녕하세요. 오늘은 0의 개수를 세어볼 거에요.

문제

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

아이디어

nCk에서의 2의 개수와 5의 개수를 세어주면 됩니다. 이때 개수를 세는 가장 편한 방법은 조합의 팩토리얼 형식에서 2로 계속 나누고 5로 계속 나누어서 세는것이 편합니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll cal(ll x, ll num)
{
	ll cnt = 0;
	while (x)
	{
		cnt += x / num;
		x /= num;
	}
	return cnt;
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll N, M, M2, cnt = 0, cnt2 = 0;

	cin >> N >> M; M2 = N - M;

	cnt = cal(N, 2) - cal(M, 2) - cal(M2, 2);
	cnt2 = cal(N, 5) - cal(M, 5) - cal(M2, 5);

	cout << min(cnt, cnt2);
}

감사합니다.