[BaekJoon][2004] 조합 0의 개수

BAEKJOON ONLINE JUDGE

2004 조합 0의 개수

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

 

조합 nCm의 0의 개수는

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

이는 (n!의 min(2개수, 5개수) - ((m!의 min(2개수, 5개수) + ((n - m)!의 min(2개수, 5개수))를 하여 구할 수 있다.

n!의 2의 개수, 5의 개수 구하는 방법은 [1676 팩토리얼 0의 개수] 참고

위 참고에서 첫 번째 개수를 구하는 방법으로는 [2004 조합 0의 개수]문제를 풀 수가 없다. (문제의 입력 범위가 매우 크기 때문에 time limit가 난다.

따라서 두번째 제시한 방법으로 구하면 아무런 문제 없이 문제를 풀 수 있다.

#include <stdio.h>
 
long long int two[3];
long long int five[3];
 
long long int mymin(long long int first, long long int second)
{
    if (first < second)    return first;
    return second;
}
 
void process(long long int number, int flag)
{
    long long int i;
    long long int t = 0, f = 0;
 
    for (i = 2; i <= number; i *= 2)
        t += number / i;
 
    for (i = 5; i <= number; i *= 5)
        f += number / i;
 
    two[flag] = t;
    five[flag] = f;
}
 
int main()
{
    long long int n, m;
 
    scanf("%lld %lld", &n, &m);
 
    process(n, 0);
    process(m, 1);
    process(n - m, 2);
 
    printf("%lld\n", mymin(two[0] - two[1] - two[2], five[0] - five[1] - five[2]));
 
    return 0;
}