백준 2004 조합 0의 개수

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

2004번: 조합 0의 개수

백준 2004 조합 0의 개수는 조합의 결과가 제일 뒤 0의 개수가 몇개가 나오는지 확인하는 문제이다. 1676번 팩토리얼의 0의 개수와 같듯이 2, 5의 등장횟수를 구한 뒤 적은 등장 횟수가 답이된다. 왜냐하면 2*5가 한개씩 있으면 10이되고 두개씩 있으면 100이되면서 뒤의 숫자들은 2와 5의 개수로 결졍된다. 

 

 

 

조합은 아래와 같은 공식을 따른다. 

그래서 우리는 n!, (n-r)!, r!에 5와 2가 몇번 등장해야하는지 확인해야한다.

 

예를 들어 25!이면 1 부터 25까지의 곱셈을 의미한다.

 

그럼 5의 등장 횟수는  

5, 10, 15, 20, 25

 

25는 5^2임으로 총 6번 등장한다. 이럿듯 결국 5로 나누어주고 25로 나누어 주어서 횟수를 구하면 된다(5의 제곱승). 분모의 경우도 동일하게 n-r의 등장 횟수 r의 등장횟수를 더한 다음 n의 등장횟수에서 빼주면 조합결과에서 5의 등장횟수가 된다. 2도 마찬가지로 위와 같은 방법으로 2의 등장횟수를 구한 후 더 등장횟수가 적은 값이 0의 등장횟수가 된다. 

 

코드

#include <cstdio>
#include <algorithm>

using namespace std;

long long M, N;

long long divide5(long long number);
long long divide2(long long number);

int main(){
	scanf("%lld %lld", &N, &M);
	printf("%lld", min( divide5(N) - (divide5(M) + divide5(N-M)), divide2(N) - (divide2(M) + divide2(N-M))));
}

long long divide5(long long number){
	long long appendix = 0;
	for(long long i = 5; i <= number; i=i*5)
		appendix+=number/i;
	return appendix;
}
long long divide2(long long number){
	long long appendix = 0;
	for(long long i = 2; i <= number; i=i*2)
		appendix+=number/i;
	return appendix;
}