백준 2004 - 조합 0의 개수

문제

 

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

2004번: 조합 0의 개수

 

 

풀이

 

10의 배수들이 끝자리가 0이 된다. 10은 2x5로 이루어진다. 따라서 조합의 결과 값에서 2와 5의 개수를 구하면 된다. 2와 5의 각 개수 중 적은 값이 만들 수 있는 0의 수가 된다. nCm = n! / (m! * (n-m)!) 이므로 nCm을 한 이후에 2와 5의 개수를 구하면은 시간초과가 발생한다. 따라서 각각을 따로 구한다.

1. n!에서 2, 5의 개수

2. m!에서 2, 5의 개수

3. (n-m)!에서 2, 5의 개수

 

1번에서 2, 3번에 대해 각각 뺄셈을 진행한 후에 2와 5의 개수 중 최소값이 끝자리 0의 개수가 된다.

 

n!에서 2의 개수(or 5의 개수)를 구하는 빠른 방법은 2(or 5)^i (i=1, 2, 3, ...)로 나눈 몫이 0이 아닐때까지 몫을 계속 더해주면 된다. 

 

코드

 

#include <iostream>
 
using namespace std;
 
int n, m;
 
long long get(int a, int b)
{
    long long r = 0;
    long long d = b;
    while (a / d)
    {
        r += a / d;
        d *= b;
    }
    return r;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> n >> m;
 
    int k = n - m;
 
    long long two = get(n, 2) - get(m, 2) - get(k, 2);
    long long five = get(n, 5) - get(m, 5) - get(k, 5);
 
    cout << (two < five ? two : five);
 
    return 0;
}