[백준 2004] 조합 0의 개수

www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

조합에서 끝자리 0의 개수를 구하는 문제

2와 5의 개수 중 작은 값을 리턴하면 되는 쉬운 문제이나 값의 범위가 long long이므로 while문을 돌려서 모두 확인하면 시간초과가 발생할 것이다.

 

그래서 사용하는 방법!

n!에서 2의 개수와 5의 개수를 구할 것인데 다음과 같은 방법을 사용한다.

 

n=10이라 가정하면

1 2 3 4 5 6 7 8 9 10 을 곱한 값이 10!이다.

이 때 2의 개수를 찾고 싶다면 10을 2의 제곱수로 나눈값을 더해주면 된다.

1. 10까지의 숫자에서 2의 배수는 5개이다. 10/2를 더한다.

2. 2를 한개만 가진 숫자는 모두 지워졌다. 하지만 2^2, 2^3과 같이 2가 여러개인 경우 2가 더 남아있으므로 10/4를 더해서 4의 배수를 지워준다.

3. 마지막으로 8의 배수를 지워준다. +=10/8

 

알고리즘을 일반화하면 구하는 숫자를 i라고 할 때

1. cnt += n/i

2. cnt += n/(i*i)

3. cnt += n/(i*i*i)

...

이런 식으로 진행되는 것이다. 

 

nCk = n! / (n-k)! k!이므로 다음과 같이 코드를 작성 가능하다. 

#include <stdio.h>

#define ll long long

using namespace std;
ll n, r;

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

  ll two = 0, five = 0;

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

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

  for (ll i = 2; i <= r; i *= 2)
  {
    two -= r / i;
  }

  for (ll i = 5; i <= r; i *= 5)
  {
    five -= r / i;
  }

  for (ll i = 2; i <= n - r; i *= 2)
  {
    two -= (n - r) / i;
  }

  for (ll i = 5; i <= n - r; i *= 5)
  {
    five -= (n - r) / i;
  }

  ll res = five < two ? five : two;
  printf("%lld\n", res);
  return 0;
}