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

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

2004번: 조합 0의 개수

조합의 끝자리 0의 개수를 출력하는 문제이다.

 

끝자리 0의 개수를 새기위해선 식에 10이 몇번 곱해져있는가를 구하면 되는데 이건 식에 2와 5가 곱해진 횟수중 더 작은 것의 횟수와 같다. (2와 5의 곱이 10이므로)

nCm = n! / (n-m)!m! 이므로  n!에 곱해져있는 2의 횟수와 5의 횟수에 각각 (n-m)!와 m!에 곱해져있는 2의 횟수와 5의 횟수를 빼면 된다.

 

2의 횟수와 5의 횟수를 새는 방법은 예를 들어 24!의 2의 갯수와 5의 갯수를 샌다고 가정하면 

2의 갯수는 (24/2) + (24/4) + (24/8) + (24/16) = 12 + 6 + 3 + 1 = 22 이다.

2의 1제곱부터 K제곱까지로 n를 나눈 수들을 더해주면 되는데 이때 K는 (2^K <= n)를 만족하는 K까지이다.

 

5의 갯수를 구하는 방법도 이와같다.

 

이런 방법을 이용해서 n!의 2와 5의 갯수에서 (n-m)!과 m!의 2와 5의 갯수를 뺀 뒤 결과적으로 나온 2와 5의 갯수중 더 작은 수를 출력해주면 정답이다.

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
long long two_ret=0, five_ret=0;

void get_zero_plus(long long N)
{
    long long two=2, five=5;
    while(two<=N)
    {
        two_ret += N/two;
        two*=2;
    }
    while(five<=N)
    {
        five_ret += N/five;
        five *= 5;
    }
    return;
}

void get_zero_minus(long long N)
{
    long long two=2, five=5;
    while(two<=N)
    {
        two_ret -= N/two;
        two*=2;
    }
    while(five<=N)
    {
        five_ret -= N/five;
        five *= 5;
    }
    return;
}

int main()
{
    long long  n, m;
    scanf("%lld %lld",&n,&m);

    get_zero_plus(n);
    get_zero_minus(n-m);
    get_zero_minus(m);

    printf("%lld",min(two_ret, five_ret));

    return 0;
}