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

문제

 

---

풀이

 

myunji.tistory.com/231?category=1154147

[백준] 1676번 : 팩토리얼 0의 개수

이 문제의 풀이를 거의 그대로 사용할 것이다.

nCm = n!/(m!(n-m)!)이다.

그니까 n!과 m!, 그리고 (n-m)!의 2와 5의 수를 각각 구한 뒤, 나눗셈 곱셈을 잘 고려해 계산하면 되겠다.

---

소스코드

 

#include <iostream>
#include <algorithm>
using namespace std;

pair<long long, long long> binomial(long long n) {
    int two_cnt = 0, five_cnt = 0;

    for (long long i = 2; i <= n; i *= 2)
        two_cnt += n / i;
    for (long long i = 5; i <= n; i *= 5)
        five_cnt += n / i;
    return pair<long long, long long>(two_cnt, five_cnt);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m;

    cin >> n >> m;
    pair<long long, long long>p1 = binomial(n); //n!
    pair<long long, long long>p2 = binomial(m); //m!
    pair<long long, long long>p3 = binomial(n - m); //(n-m)!
    long long two = p1.first - p2.first - p3.first;
    long long five = p1.second - p2.second - p3.second;
    cout << min(two, five);
}