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

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

2004번: 조합 0의 개수

n!에서 2와 5의 개수(1)와 k!과 (n-k)!에서 2와 5의 개수(2)를 구하면 0의 개수를 알 수 있다.

(1) - (2)를 한 뒤, 2의 개수와 5의 개수 중 작은 쪽의 개수가 0의 개수이다.

 

원하는 수가 몇번 나왔는지 구하는 cnt 함수를 작성한다.

10!에서 2의 개수를 구해보자.

 

10/2 = 5개 - 2,4,6,8,10 (2^1)

5/2 = 2개 - 4, 8 (2^2)

2/2 = 1개 - 8 (2^3)

 

(2의 배수를 카운팅)

---

#include<string>
#include<iostream>

using namespace std;

int cnt(int n, int r) {
    int count = 0;
    while (n) {
        n /= r;
        count += n;
    }

    return count;
}

int main() {
    unsigned long int n, m;

    cin >> n >> m;

    //2랑 5가 짝지어지는 횟수가 0의 개수
    int n_two = cnt(n, 2);
    int n_five = cnt(n, 5);

    int nm_two = cnt(n - m, 2);
    int nm_five = cnt(n - m, 5);

    int m_two = cnt(m, 2);
    int m_five = cnt(m, 5);

    int two = n_two - (nm_two + m_two);
    int five = n_five - (nm_five + m_five);

    if (two <= 0 || five <= 0) {
        cout << 0;
    }
    else if (two >= five) {
        cout << five;
    }
    else if (two <= five) {
        cout << two;
    }

    return 0;
}