BOJ 2004 조합 0의 개수

https://www.acmicpc.net/problem/2004
시간 2초, 메모리 128MB
input :

• n m (0 <= m <= n <= 2000000000, n != 0)

output :

• 의 끝자리 0의 개수 구하기

---

팩토리얼로 모두를 계산하면 시간초과가 발생한다.
좀 색다른 방법이 필요한데
다른 사람들의 풀이에서 다들 10을 구성하는 2와 5를 찾아서 둘 중 min 값을 출력해줬다.. 왜 일까 하는 생각이 제일 먼저 듦;;;

현재 7C3을 계산하려 할 때
분자에 7. 6. 5. 4. 3. 2. 1 분모에 (3. 2. 1) * (4. 3. 2. 1)
분자의 경우 2: 4개 5: 1개
분모에 2: 4개
--> 5만 1개 존재, 2는 0개 둘 중 최솟값을 출력하니까 0개가 나오게 됨.

그렇다면 7에서 2를 4개 얻으려면 어떻게 해야 하나.
7이 0이될 때 까지 2로 나누면 이 값을 얻을수 있다.
5도 이와 같다.

import sys


def five(a):
    ret = 0
    while a != 0:
        a //= 5
        ret += a
    return ret


def two(a):
    ret = 0
    while a != 0:
        a //= 2
        ret += a
    return ret


n, m = map(int, sys.stdin.readline().split())
if m == 0:
    print(0)
else:
    print(min(two(n) - two(m) - two(n - m), (five(n) - five(m) - five(n - m))))