백준 2004 c++ 조합 0의 개수

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

2004번: 조합 0의 개수

 

N=25, M=12의 경우 조합 값의 마지막 2자리가 0이므로 2가 출력 되어야 한다.

조합값을 소인수 분해 했을 때 10의 개수를 구하기 위해 2의개수, 5의개수를 찾는다

구간을 N, N-M, M으로 나누고 지수의 성질을 이용해 분자의 2,5의개수 - 분모의 2,5의 개수를 적용

#include <iostream>
using namespace std;

long long count2(long long n) //2의 개수를 찾는 함수
{
	long long result=0;
	for (long long i = 2; i <= n; i *= 2)//2의 배수만을 훑는다
	{
		long long cnt = n / i;//2로 나누었을 때 몫이 곧 2의 개수
		result += cnt;
	}
	return result;
}

long long count5(long long n)//5의 개수를 찾는 함수
{
	long long result = 0;
	for (long long i = 5; i <= n; i *= 5)
	{
		long long cnt = n / i;
		result += cnt;
	}
	return result;
}

int main()
{
	long long N, M;
	cin >> N >> M;
	int result = min(count2(N)-count2(N - M) - count2(M), count5(N) - count5(N - M) - count5(M));
	cout << result;//min(분자의 2,5의 개수) - min(분모의 2,5의 개수)
}