[백준 Python] - 2004 조합 0의 개수

1. 문제 - 2004번

2. 접근법

이전 1676번 문제를 풀 때처럼 문자열을 활용한 방법으로 풀려 하니 도저히 풀리지 않았다.
계속 고민해봐도 방법을 모르겠어서 찾아보니, 다른 분들의 블로그에서 아래와 같은 원리를 활용해 문제를 풀 수 있었다.

1676번을 빠르게 푸는 방법을 알아야 이 문제를 풀 수 있다.
특히, 다음 블로그의 글이 이해하는데 도움이 되었다.
https://lucian-blog.tistory.com/84

이 문제의 경우,

- 문제가 의마하는 바는 n과 m의 조합 값이 가지는 0의 개수를 구하는 것
- 0의 개수를 구하기 위해서는 2와 5의 지수의 개수로 각각 0의 개수를 구할 수 있으며 그 중 작은 값을 찾아주면 됨(일종의 교집합)
- n과 m의 조합 값에서의 0의 개수는 n!의 0의 개수 - (n-m)!의 0의 개수 - m!의 0의 개수 
(n!/(n-m)!m! 이므로, 분모의 n!에서 분자의 0이 나눠지기 때문)

 <정답 코드>

import sys
input = sys.stdin.readline

def count2(n):
    count = 0
    while n != 0:
        n //= 2
        count += n

    return count

def count5(n):    
    count = 0
    while n != 0:
        n //= 5
        count += n
    return count

n, m = map(int, input().split())
two_count = count2(n) - count2(n-m) - count2(m)
five_count = count5(n) - count5(n-m) - count5(m)
print(min(two_count, five_count))