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

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

2004번: 조합 0의 개수

 본 문제는 nCm의 끝자리 0의 개수를 출력하는 문제다. 문제의 크기가 2,000,000,000 이므로 long long 자료형을 써야 하며 조합을 직접 계산해서 0의 개수를 출력하는 것은 불가능하다. 따라서, 다음과 같은 절차로 코딩을 해야 한다.

1. 5 ~ n까지 5의 배수를 5로 나누었을 때 몫의 합
2. 2 ~ n까지 2의 배수를 2로 나누었을 때 몫의 합
3. 5 ~ (n-m)까지 5의 배수를 5로 나누었을 때 몫의 합
4. 2 ~ (n-m)까지 2의 배수를 2로 나누었을 때 몫의 합
5. (1번의 결과) - (3번의 결과)
6. (2번의 결과) - (4번의 결과)
7. (5번의 결과), (6번의 결과) 중 작은 값 출력

#include <cstdio>
 
using namespace std;
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int cnt2 = 0, cnt5 = 0;
    for (long long i = 5; i <= n; i *= 5) cnt5 += n / i;
    for (long long i = 5; i <= m; i *= 5) cnt5 -= m / i;
    for (long long i = 5; i <= n-m; i *= 5) cnt5 -= (n-m) / i;
    for (long long i = 2; i <= n; i *= 2) cnt2 += n / i;
    for (long long i = 2; i <= m; i *= 2) cnt2 -= m / i;
    for (long long i = 2; i <= n-m; i *= 2) cnt2 -= (n-m) / i;
    int ans = cnt2<cnt5 ? cnt2:cnt5;
    printf("%d", ans);
}