BOJ 1676 팩토리얼 0의 개수BOJ 2004 조합 0의 개수 (0의 개수)

두 문제 모두 결국 팩토리얼의 0의 개수를 세야 하는 문제다.

팩토리얼

우선 쉽게 구할 수 있는 팩토리얼의 0의 개수부터 생각해보자. 2와 5가 곱해져야 0이 생기고, 팩토리얼의 결과를 소인수분해하면 5의 지수가 2의 지수보다 작을 것이므로 결국 팩토리얼 계산 중 곱해지는 5의 개수를 세면 된다.

def get_5_cnt(n: int):
    i = 5
    answer = 0
    while n >= i:
        answer += n // i
        i *= 5
    return answer

주어진 수를 $5$로 나눈 몫, $5^2$로 나눈 몫, $5^3$으로 나눈 몫을 순서대로 구해서 다 더하면 된다.

조합

조합의 경우 $n\choose{m}$를 구하는 공식이 $\frac{n!}{m!(n-m)!}$로 정해져 있으므로 이를 이용하자. $n!$, $m!$, $(n-m)!$의 2의 개수와 5의 개수를 모두 구한 후 적절히 계산하면 된다. 5의 개수를 이용하는 식은 위의 식을 그대로 사용하고, 2의 개수를 이용하는 식은 새로 쓴다.

def get_2_cnt(n: int):
    i = 2
    answer = 0
    while n >= i:
        answer += n // i
        i *= 2
    return answer

이후 $m!$과 $(n-m)!$의 값의 합을 $n!$의 값에서 빼주면 답이 된다.

n_5_cnt = get_5_cnt(n)
n_2_cnt = get_2_cnt(n)

m_5_cnt = get_5_cnt(m)
m_2_cnt = get_2_cnt(m)

n_m_5_cnt = get_5_cnt(n - m)
n_m_2_cnt = get_2_cnt(n - m)

cnt_5 = n_5_cnt - (m_5_cnt + n_m_5_cnt)
cnt_2 = n_2_cnt - (m_2_cnt + n_m_2_cnt)
answer = min(cnt_2, cnt_5)

마지막에 min을 사용하는 이유는 2가 3개 남고 5가 4개 남을 경우 $n\choose{m}$에 0을 3개만 있을 것이기 때문이다. 팩토리얼의 경우와 다르게 조합의 경우 반드시 5가 더 적을 것이라고 확신할 수 없기 때문에 위와 같이 풀어야 한다.

정답 코드(2004)

import sys

input = sys.stdin.readline


def get_2_cnt(n: int):
    i = 2
    answer = 0
    while n >= i:
        answer += n // i
        i *= 2
    return answer


def get_5_cnt(n: int):
    i = 5
    answer = 0
    while n >= i:
        answer += n // i
        i *= 5
    return answer


n, m = map(int, input().split())
n_5_cnt = get_5_cnt(n)
n_2_cnt = get_2_cnt(n)
m_5_cnt = get_5_cnt(m)
m_2_cnt = get_2_cnt(m)
n_m_5_cnt = get_5_cnt(n - m)
n_m_2_cnt = get_2_cnt(n - m)
cnt_5 = n_5_cnt - (m_5_cnt + n_m_5_cnt)
cnt_2 = n_2_cnt - (m_2_cnt + n_m_2_cnt)
print(min(cnt_2, cnt_5))