[알고리즘/문제풀이/BOJ 2004] 조합 0의 개수

조합 0의 개수 문제는 소인수 분해시 2와 5의 개수를 활용하는 문제입니다. 팩토리얼 값을 소인수 분해했을 때 5의 개수를 구하는 방법은 팩토리얼에서 처음의 항을 5로 나눈 수 + 25로 나눈 수 + 125로 나눈 수 + .... 식과 같다. 이런 방식으로 2와 5의 개수를 찾고 그 중 가장 작은 값이 0의 개수가 된다.

작성한 코드는 다음과 같다.

---

#include<stdio.h>

long long int n, m;
long long int five, two;
long long int d;

int main(void) {
	scanf("%lld %lld", &n, &m);

	d = 5;
	while (1) {
		if ((n< d)) break;
		five += (n / d);
		d *= 5;
	}
	d = 2;
	while (1) {
		if ((n < d)) break;
		two += (n / d);
		d *= 2;
	}
	d = 5;
	while (1) {
		if ((m < d)) break;
		five -= (m / d);
		d *= 5;
	}
	d = 2;
	while (1) {
		if ((m < d)) break;
		two -= (m / d);
		d *= 2;
	}
	d = 5;
	while (1) {
		if ((n-m) < d) break;
		five -= ((n-m) / d);
		d *= 5;
	}
	d = 2;
	while (1) {
		if (((n-m) < d)) break;
		two -= ((n-m) / d);
		d *= 2;
	}
	
	if (five < two) printf("%lld\n", five);
	else printf("%lld\n", two);
}

문제의 지문은 다음의 링크에서 확인할 수 있다.

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