백준 / 수학 / 2004번 / 조합 0의 개수 / C++

문제

(nm)의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n, m (0 ≤ m ≤ n ≤ 2,000,000,000, n≠0)이 들어온다.

출력

첫째 줄에 (nm)의 끝자리 0의 개수를 출력한다.

예제 입력 1 

25 12

예제 출력 1 

2

 

#include <iostream>
using namespace std;

int countTwo(int n) {
	int cnt = 0;
	
	for(long long i=2; i<=n; i*=2) {
		cnt += n / i;
	}
	
	return cnt;
}

int countFive(int n) {
	int cnt = 0;
	
	for(long long i=5; i<=n; i*=5) {
		cnt += n / i;
	}
	
	return cnt;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m;
	int twoCnt, fiveCnt;
	int result;
	cin >> n >> m;
	
	twoCnt = countTwo(n) - countTwo(n-m) - countTwo(m);
	fiveCnt = countFive(n) - countFive(n-m) - countFive(m);
	
	result = twoCnt > fiveCnt ? fiveCnt : twoCnt;
	
	cout << result << '\n';
		
	return 0;
}

---

n!의 0의 갯수 = 10이 몇번이나 제곱을 했는지 = n!의 2 * 5의 갯수

팩토리얼의 0의 개수를 구하는것은 전의 포스팅에서 다뤘으니 참고 바랍니다.

2021.08.05 - [ALGORITHM/백준] - 백준 / 수학 / 1676번 / 팩토리얼 0의 개수 / C++

백준 / 수학 / 1676번 / 팩토리얼 0의 개수 / C++

 

일단 조합이라는 식은 nCr이다.

nCr = n! / ((n-r)! * r!)

위 문제에서는 n, m을 입력을 받았으니 nCm의 0의개수를 구한다고 생각하면 된다.

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

하지만 진짜 팩토리얼을 구해서 하면 시간초과나 범위를 벗어나 컴파일 에러가 날 것 이므로,

우리는 갯수만 구해서 식을 사용해주면 된다.

 

일단 0의 갯수는 10의 제곱수인데 2 * 5가 쌍이 이루어져야 한다.

만약 두 수 a, b가 있다고 하자.

그럼 a! * b!의 0의 갯수는 (a!의 2의 갯수 + b!의 2의 갯수)와 (a!의 5의 갯수 + b!의 5의 갯수)를 비교해서

작은것의 수 일것이다.

왜냐하면 예를들어 a!을 소인수 분해시 2 * 5의 짝을 이루고 남는 2와 b!을 소인수 분해시 2 * 5의 짝을 이루고 남는 5가

곱해질 시 서로 짝을 이루어 새로운 10을 만들어 낼 수 있기 때문이다.

따라서 2의 갯수와 5의 갯수 모두 구해야 한다.