백준 2004번 : 조합 0의 갯수

문제 링크 : https://www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

 

 문제 설명 

 

1.n과 m 이 주어질때 ,  nCm 의 끝자리 0의갯수를 출력하면됨.

 

 알고리즘 

 

1. nCm = n!/(m!(n-m)!) 을 이용하여 풀어야함

2. n! 에서 2의 개수와 5의개수를 구하고 m!의 2의개수와 5의개수 (n-m)!의 2의개수와 5의 개수를 각각구한다 .

3. 분모의 2의개수와 5의개수에서 분자의 2의개수와 5의개수를 뺸뒤 2의 개수와 5의개수중 작은 수를 출력한다.

   끝자리가 0이되기위해서는 2와 5가 각각하나씩 필요하기 때문에 작은수를 출력하면됨 

4. 각각의 2와 5의개수를 구하는 코드가 전혀 떠오르지않아 블로그를 참고함

 

블로그주소 : https://jaimemin.tistory.com/908

 

 

 코 드 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
 
pair<ll, ll > func(ll  N)
{
    ll  two = 0, five = 0;
    // N! 에서 2의 의갯수 
    for (ll i = 2; i <= N; i *= 2)
        two += N / i;
 
    //N! 에서 5의 갯수 
    for (ll i = 5; i <= N; i *= 5)
        five += N / i;
    return { two, five };
 
}
 
 
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll  N, M;
    cin >> N >> M;
    vector<pair<ll, ll >> v(3);
 
    v[0] = func(N); //N!
    v[1] = func(M); //M!
    v[2] = func(N - M); //(N-M)!
    ll f = v[0].first - v[1].first - v[2].first;
    ll t = v[0].second - v[1].second - v[2].second;
 
    //맨뒤가 0이되려면 5와 2각각 하나씩 필요하므로 둘중 작은수를 출력.
    cout << min(f, t);
    
 
}