[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 조합 0의 개수 (2004)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 조합 0의 개수 (2004)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 조합 0의 개수 (2004)

 

---

2004번: 조합 0의 개수

[ 문제 ]

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

[ 입력 ]

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

[ 출력 ]

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

 

---

[ 코드 ]

#include <iostream>
using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	long long two = 0, five = 0;
	long long n, m;
	cin >> n >> m;

	// x!의 n의 소인수 개수를 구하는 법. 
	// x를 n으로 나눔 + x를 n^2으로 나눔 ... + x를 n^m으로 나눔

	for (long long i = 2; i <= n; i *= 2)
	{
		two += n / i;
	}

	for (long long i = 2; i <= n-m; i *= 2)
	{
		two -= (n-m) / i;
	}

	for (long long i = 2; i <= n; i *= 2)
	{
		two -= m / i;
	}

	for (long long i = 5; i <= n; i *= 5)
	{
		five += n / i;
	}

	for (long long i = 5; i <= n; i *= 5)
	{
		five -= (n-m) / i;
	}

	for (long long i = 5; i <= n; i *= 5)
	{
		five -= m / i;
	}

	cout << min(two, five) << '\n';

	return 0;

}

---

* 유의사항 - 아직 공부하고 있는 문과생 코린이가, 정리해서 남겨놓은 정리 및 필기노트입니다. - 정확하지 않거나, 틀린 점이 있을 수 있으니, 유의해서 봐주시면 감사하겠습니다. - 혹시 잘못된 점을 발견하셨다면, 댓글로 친절하게 남겨주시면 감사하겠습니다 :)