BOJ 2004번 :: 조합 0의 개수

#문제

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

2004번: 조합 0의 개수

 

#작성 코드

#include <iostream>
using namespace std;
 
int main(){
    int n, m;
    int two=0, five=0;
    // 입력 
    cin>>n>>m;
    // N!
    for(long long i=2; i<=n; i*=2)
        two += n/i;
    for(long long i=5; i<=n; i*=5)
        five += n/i;
 
    // M!
    for(long long i=2; i<=m; i*=2)
        two -= m/i;
    for(long long i=5; i<=m; i*=5)
        five -= m/i;
 
    // (N-M)!
    for(long long i=2; i<=n-m; i*=2)
        two -= (n-m)/i;
    for(long long i=5; i<=n-m; i*=5)
        five -= (n-m)/i;
    
    // 결과 출력 
    int result=min(two, five);
    cout<<result<<'\n';
    return 0;
}

##

nCm은 n! / ( m! * (n-m)! ) 이므로

n!에 포함된 2와 5의 개수 - m!에 포함된 2와 5의 개수 - (n-m)!에 포함된 2와 5의 개수 => min(2의 개수, 5의 개수) 가 nCm에 포함된 0의 개수이다.

 

n!에 i가 약수로 몇 개 들어있는가?

tmp = 2, ... , n으로 반복.

i개수 = i개수 + tmp/i;

i = i*i;

i<=n까지 반복한다.

 

ex) n=20일 경우, 2가 인수로 몇 개 들어있을까

i = 2          : 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 -> 10개

i = 4          : 4, 8, 12,16, 20                                 -> 5개

i = 8          : 8, 16                                                   -> 2개

i = 16        : 16                                                        -> 1개

총 18개 들어있다.