[BOJ 2004] 조합 0의 개수

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

불러오는 중입니다...

---

nCm에서 끝자리 0의 개수를 구하는 문제이다.

 

nCm = 

이다.

 

즉, 

(n!의 0의 개수 - (m!의 0의 개수 + (n-m)!의 0의 개수)))  .........⑴

를 구해야 한다.

 

끝자리의 0의 개수는 nCm이 인수로 10을 몇 개를 가지는지를 구해야 한다.

 

10 = 2 * 5이므로 2와 5의 개수를 구하면 된다.

 

팩토리얼에서 0의 개수는 [팩토리얼 0의 개수]를 통해 구하면 된다.

 

하지만 위와는 다르게 5의 개수뿐만 아니라 2와 5의 개수를 모두 구해야 한다.

 

왜냐하면 위에서는 N! 하나만 구하면 되지만, 이 문제에서는 ⑴식에서 뺼셈이 존재하기 때문이다.

---

#include <stdio.h>
#define ll long long int
 
 
int main()
{
    ll n, m;
 
    /*
        순서대로
        분자: n! , 분모: m! , (n-m)!
        의 (숫자)의 개수
    */
    ll fc = 0, fp1 = 0, fp2 = 0;// 5의 개수
    ll sc = 0, sp1 = 0, sp2 = 0;// 2의 개수
 
    scanf("%lld %lld", &n, &m);
 
    for (ll i = 5; i <= n; i *= 5)
    {
        fc += n / i;
 
        if (i <= m)
        {
            fp1 += m / i;
        }
        if (i <= (n - m))
        {
            fp2 += (n - m) / i;
        }
    }
 
    for (ll s = 2; s <= n; s *= 2)
    {
        sc += n / s;
 
        if (s <= m)
            sp1 += m / s;
        if (s <= (n - m))
            sp2 += (n - m) / s;
    }
 
    ll fresult = fc - fp1 - fp2;
    ll sresult = sc - sp1 - sp2;
 
    printf("%lld", fresult > sresult ? sresult : fresult);
}