[C++] 백준 2004번 조합 0의 개수

nCm에서 끝자리 0의 개수를 찾는 문제입니다.

0의 개수는 소인수 2와 5로 찾을 수 있습니다.
소인수 2가 5개고 5가 2개면
0의 개수는 2개입니다.

1. n!에 대한 2와 5의 소인수 개수
2. (n - m)!에 대한 2와 5의 소인수 개수
3. m!에 대한 2와 5의 소인수 개수

(1.) - (2.) - (3.)을 해주면 2와 5의 개수를 구할 수 있습니다.
여기서 2와 5중 적은 것을 출력해줍니다.

소인수를 구하는 법은
x를 n으로 나눔
x를 n^2로 나눔,
x를 n^3로 나눔,
.....
x를 n^m-1로 나눔
x를 n^m로 나눔
나눈 값들을 전부 더하면 소인수의개수를 구할 수 있습니다.

 

 

#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

long long func(int n, int x)
{
	int num = 0;

	for (long long i = x; n / i >= 1; i *= x) {
		num += n / i;
	}

	return num;
}

int main(int argc, char *argv[])
{
	int n, m;

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

	five = func(n, 5) - func(n - m, 5) - func(m, 5);
	two = func(n, 2) - func(n - m, 2) - func(m, 2);

	cout << min(five, two) << endl;

	return 0;
}