[C++] BOJ 2004 조합 0의 개수

 

 

문제 출처

백준 온라인 저지

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

2004번: 조합 0의 개수

 

문제 

 

입 / 출력

 

풀이

조합의 공식이 n! / m! (n-m)! 이기 때문에

분자와 분모를 소인수 분해 했을 경우 

• 분자가 가진 5의 개수 - 분모가 가진 5의 개수
• 분자가 가진 2의 개수 - 분모가 가진 2의 개수

중에서 더 작은 값을 구하면 답을 구할 수 있다.

 

코드

#include <iostream>

using namespace std;

long long n, m;

long long div5(long long n) {
  long long cnt = 0;
  for (long long i = 5; i <= n; i *= 5)
    cnt += n / i;

  return cnt;
}

long long div2(long long n) {
  long long cnt = 0;
  for (long long i = 2; i <= n; i *= 2)
    cnt += n / i;

  return cnt;
}

int main() {
  cin >> n >> m;
  long long five = div5(n) - div5(n - m) - div5(m);
  long long two = div2(n) - div2(n - m) - div2(m);
  cout << min(five, two) << "\n";
}