백준 2004 파이썬 (조합 0의 개수)

문제 : https://www.acmicpc.net/problem/2004

• 이 문제는 팩토리얼 0의 개수 문제와는 약간 다르다 (끝자리가 0 -> 10의 배수 (2x5))
• 조합의 경우 최종적인 값은 팩토리얼 형태가 아니므로 5의 개수만 고려해서는 안된다. 이 경우에는 분자와 분모 각각 팩토리얼로 이루어져 있긴 하지만 나눠지면서 2와 5의 개수의 규칙에 변동이 생기기 때문이다.
• 결론적으로 2와 5 짝이 맞아야 10이 되므로 2의 개수와 5의 개수중 더 작은게 10의 개수이다.
  해당 공식을 활용하여
  2의 개수 = n!의 2의 개수 - (n-r)!의 2의 개수 - r!의 2의 개수
5의 개수 = n!의 5의 개수 - (n-r)!의 5의 개수 - r!의 5의 개수
  이러한 두 가지 식을 도출해낼 수 있다.

💻 Code

import sys
a,b = map(int, sys.stdin.readline().split())

# 2와 5의 개수세기 (m 자리에 2, 5)
def count(n, m):
   if n < m:
       return 0
   
   count = 0
   while n >= m:
       count += n // m
       n = n // m
   return count

two_count = count(a,2) - count(a-b,2) - count(b,2)
five_count = count(a,5) - count(a-b,5) - count(b,5)
print(min(two_count, five_count))

풀이,코드 출처