combinationzero

문제

n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.

nCm은 수식으로 n!/m!(n-m)! 으로 구할 수 있다. (5! = 1 * 2 * 3 * 4 * 5)

n과 m이 주어졌을때 nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.  

입력

첫째 줄에 정수 n, m(0≤m≤n≤1,000,000)이 들어온다.

 

출력

첫째 줄에 0의 개수를 출력한다.

 

예제 입력

25 12

예제 출력

2

 

#코드

import sys
 
 
if __name__ == "__main__":
  input = sys.stdin.readline
  n, m  = map(int, input().split())
  
  two_cnt  = 0
  five_cnt = 0
  
  # n!/m!(n-m)!
  
  # n! 즉 각각의 숫자 속의 2와 5를 구한다.
  for i in range(2, n+1):
    temp_num = i
    while temp_num%2 == 0 or temp_num%5 == 0:
      if temp_num%2 == 0:
        two_cnt += 1 # 분자이니깐 (+) 해준다.
        temp_num //= 2
      if temp_num%5 == 0:
        five_cnt += 1 # 분자이니깐 (+) 해준다.
        temp_num //= 5
        
  # m! 즉 각각의 숫자 속의 2와 5를 구한다.      
  for i in range(2, m+1):
    temp_num = i
    while temp_num%2 == 0 or temp_num%5 == 0:
      if temp_num%2 == 0:
        two_cnt -= 1 # 분모니깐 (-) 해준다.
        temp_num //= 2
      if temp_num%5 == 0:
        five_cnt -= 1 # 분모니깐 (-) 해준다.
        temp_num //= 5
        
  #(n-m)!  
  for i in range(2, n-m+1):
    temp_num = i
    while temp_num%2 == 0 or temp_num%5 == 0:
      if temp_num%2 == 0:
        two_cnt -= 1 # 분모니깐 (-) 해준다.
        temp_num //= 2
      if temp_num%5 == 0:
        five_cnt -= 1 # 분모니깐 (-) 해준다.
        temp_num //= 5
  
 
  resNum = min(two_cnt, five_cnt)
  print(resNum)