백준 2004번 - 조합 0의 개수

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

2004번: 조합 0의 개수

조합의 공식이

n! / m! * (n-m)! 이다.

여기서 끝자리 0이라는 이야기는 10이 곱해졌다는 소리이고

10을 만드는 것은 2와 5이다.

그렇기에 2와 5의 갯수를 통해 10의 갯수를 유추할 수 있다.

물론 10이 되려면 2와 5가 둘 다 필요하니 이 둘 중 최소 갯수를 출력해주면 된다.

m과 n의 범위가 크기에 long long으로 처리했다.

추가적으로 예를 들어 25의 경우 5가 두 개나 된다.

그렇기에 단순히 if(%5 == 0) 해서 five++를 해서는 안된다.

몫 연산자를 활용해서 갯수만큼 더해주었다.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
pair<ll, ll> count_two_five(int a)
{
	ll two = 0, five = 0;
	
	for (ll i = 2; i <= a; i *= 2)
		two += (a / i);

	for (ll i = 5; i <= a; i *= 5)
		five += (a / i);
	

	return make_pair(two, five);
}

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

	pair<ll, ll> n_fac = count_two_five(n);
	pair<ll, ll> m_fac = count_two_five(m);
	pair<ll, ll> n_m_fac = count_two_five(n - m);

	ll a = n_fac.first - (m_fac.first + n_m_fac.first);
	ll b = n_fac.second - (m_fac.second + n_m_fac.second);

	cout << min(a, b);

	return 0;
}