[2004] 조합 0의 개수

2004번: 조합 0의 개수

 

분석

• 조합 = nCm = n!/(m!*(n-m)!)
• 조합을 구해서 답을 내는 것이 아닌 조합 내의 0의 개수를 구하는 문제
• 끝자리가 0이라는 것은 10의 배수
  • 10의 개수 = 2의 개수와 5의 개수 중 작은 것의 개수 (2와 5가 짝을 이뤄 10이되기 때문)
    
    • n!가 가지고 있는 2의 개수 - m!이 가지고 있는 2의 개수 - (n-m)!이 가지고 있는 2의 개수
    • n!가 가지고 있는 5의 개수 - m!이 가지고 있는 5의 개수 - (n-m)!이 가지고 있는 5의 개수
    • 중에 작은 수

 

풀이 

"""
 n,m<=2,000,000,000
"""
n,m=map(int,input().split())

def count(x, k):
    cnt = 0
    while x:
        x//=k
        cnt+=x
    return cnt
    
# 2 개수
t=count(n,2)-count(m,2)-count(n-m, 2)

# 5 개수
f=count(n,5)-count(m,5)-count(n-m,5)

print(min(f,t))