[Baekjoon] 2004. 조합 0의 개수

문제 설명

문제

 (nm)$n \choose m$의 끝자리 0$0$의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n$n$, m$m$ (0≤m≤n≤2,000,000,000$0 \le m \le n \le 2,000,000,000$, n≠0$n \ne 0$)이 들어온다.

출력

첫째 줄에 (nm)$n \choose m$의 끝자리 0$0$의 개수를 출력한다.

예제 입력 1

25 12

예제 출력 1

2

문제 풀이

# 조합

• 팩토리얼로 풀이할 경우 시간초과 발생
• 끝자리가 0이라는 것은 10의 배수
• 10은 2와 5로 구성되어 있음
• 2와 5 짝이 맞아야 10이 되므로 2의 개수와 5의 개수중 더 작은게 10의 개수이다.

def count_num(N,num):
    count = 0
    while N != 0:
        N //= num
        count += N
    return count

n,m = map(int,input().split())
print(min(count_num(n,5)-count_num(n-m,5)-count_num(m,5),
            count_num(n,2)-count_num(n-m,2)-count_num(m,2)))