BOJ 2004번: 조합 0의 개수

문제 설명

nCm이 주어졌을 때, 0의 개수 구하기

🔗 문제 링크

핵심 아이디어

• 0의 개수는 곧 2와 5의 조합이므로, nCm에서 있는 2와 5의 개수 중 최솟값을 구하면 됨
• nCm = n! / (m! * (n-m)!) 공식과 각 팩토리얼에 특정 숫자가 몇 개 들어있는지 알아내는 함수를 이용하여 구하기
• 팩토리얼(n!)에서 소수 x가 몇 번 곱해져 있는지 구하는 법

  ✨ x의 거듭제곱까지 나누어야 정확한 개수를 구할 수 있음.
  
  예를 들어 25!에서 5의 개수를 셀 때, 단순히 5로 나누면 5, 10, 15, 20, 25... 이런 수들에서 각각 5가 한 번씩만 들어있다고 계산됨.
  하지만 25에는 5가 두 번 들어 있으므로 이를 반영하려면 25, 125처럼 5의 거듭제곱까지 고려해서 나누어야 정확하게 셀 수 있음.

• 나누기는 곧 2나 5 개수의 뺄셈

코드

#include <bits/stdc++.h>
using namespace std;
int n, m;

int count(int n, int x){
    int res = 0;
    for (long long i = x; i <= n; i *= x) {
        res += n / i;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    int total_5 = count(n, 5) - count(n-m, 5) - count(m, 5);
    int total_2 = count(n, 2) - count(n-m, 2) - count(m, 2);
    cout << min(total_5, total_2);
}