백준 조합 0의 개수(2004)

조합 0의 개수

1. 힌트

1) 조합을 구하는 방법은 여러 가지가 있지만 이 문제에서 $n,\ n$의 입력 범위는 최대 $2 \times 10^9$입니다. $O(n)$의 알고리즘으로도 불가능합니다.

2) $n\choose m$ $=\cfrac{nPr}{r!}$이고, $n\choose m$$\ =a \times 10^x$로 나타낼 수 있습니다.

3) $n!$을 소인수분해했을 때 $2$의 개수는 $n$을 넘지 않는 $2$의 거듭제곱수들로 $n$을 나눈 값을 더한 것 입니다.

2. 접근

1) 수식으로 표현할 수 있을까?

조합을 그대로 구하는 것이 아니라 끝에 붙은 $0$의 개수를 구하는 것에 주목합니다. $n\choose m$을 소인수분해하면 어떻게 될 지 모르겠지만 $a \times 10^x$ 꼴로 생각할 수 있고, 이 때 $x$가 $n\choose m$ 뒤에 붙은 $0$의 개수가 됩니다. $10$을 만들기 위해서는 $2$와 $5$가 하나씩 필요하므로 소인수분해했을 때 $2$와 $5$의 개수 중 작은 것이 문제의 정답이 됩니다. 소인수분해의 시간 복잡도는 단순하게 구현하면 $O(\sqrt N)$이지만 $n\choose m$의 크기를 봐서는 $O(\sqrt N)$으로도 답이 없습니다

2) 문제를 분해할 수 있을까?

$n\choose m$은 $=\cfrac{nPr}{r!}$이고, 이는 연속된 수들의 곱입니다. 만약 $n!$을 소인수분해했을 때 $2$의 개수를 알고 싶다면 $1$부터 $n$까지 수 중에서 $2$로 나누어 떨어지는 수의 개수를 구하면 될 것 같다고 생각할 수도 있습니다. 이것은 $n\ /\ 2$로 쉽게 구할 수 있습니다. 그러나 이것은 답이 아닙니다. $2^2$도 $2$로 나누어지지만 이런 방식으로 하면 $1$개씩밖에 세 주지 않기 때문입니다. $2$의 거듭제곱으로 나누어떨어지는 수들이 문제입니다. 그러므로 모든 $2$의 거듭제곱에 대해서 $n / 2^x(x \ge 1)$를 계산해서 답을 구하고 $5$도 마찬가지로 구합니다. $2^{31}$만 되어도 $2 \times 10^9$을 넘기 때문에 매우 빠를것이라 예상할 수 있습니다.
$f(x)= x!$에 포함된 $2,\ 5$의 개수 라고 정의하면
$n\choose m$ = $\cfrac{nPr}{r!}=\cfrac{\frac{n!}{(n-r)!}}{r!}=f(n)-f(n-r)-f(r)$임을 알 수 있습니다.

3. 구현

# 정수 x!을 소인수분해했을 때 2의 개수와 5의 개수 반환
def f(x):
    p = [0, 0]
    a, b = 2, 5
    while a <= x:
        p[0] += x // a
        a *= 2
    while b <= x:
        p[1] += x // b
        b *= 5
    return p

n, m = map(int, input().split())
a = f(n)
b = f(n - m)
c = f(m)
a[0] -= b[0]
a[0] -= c[0]
a[1] -= b[1]
a[1] -= c[1]

print(min(a))

1) 시간 복잡도

$f(x)$의 시간 복잡도는 $a,\ b$가 지수적으로 증가하므로 $O(lgN)$이다

2) 테스트 케이스

2000000000 1000000007
->10