재밌는 아이디어 문제 - 조합 0의 개수(실버2)

• https://www.acmicpc.net/problem/2004
• 아이디어 문제
  • 1~ N 까지 k를 약수로 갖는 수는 N//k 개
  • 저렇게 세면 k^2 같은거 k가 2개있는걸 셀 수 없으니 k를 k^2, k^3 으로 증가시키면서 갯수를 다 셈
• 만약 수를 다 곱하고 10으로 나누면서 계산을 할 경우 python 이외의 다른 언어는 자료값 초과의 수가 저장되서 에러
• for문으로 n까지 순서대로 소인수분해해서 2와 5의 갯수를 센다면 시간초과

N, M = map(int, input().split())

def func(N, k) : # N!의 k의 약수 갯수 구하기
    cnt =0
    divider = k
    while divider <= N :
        cnt += N//divider
        divider *= k
    return cnt

# nCm 의 2의 갯수
cnt2_N = func(N,2)
cnt2_M = func(M,2)
cnt2_NM = func(N-M,2)

# nCm 의 5의 갯수
cnt5_N = func(N,5)
cnt5_M = func(M,5)
cnt5_NM = func(N-M,5)

# 10 은 2와 5로 이루어져있기 때문에 min값
result = min(cnt2_N-cnt2_M-cnt2_NM, cnt5_N-cnt5_M-cnt5_NM)
print(result)