[백준] 2004번 > 조합 0의 개수

www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

문제

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

입력

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

출력

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

예제 입력 1

25 12

예제 출력 1

2

 

---

풀이

처음에는 이항계수를 factorial로 직접 계산하고 구하는 식으로하니 시간 초과가 발생했다.

def countNum(N, num): 
    count = 0 
    divNum = num 
    while( N >= divNum): 
        count = count + (N // divNum) 
        divNum = divNum * num 
    return count
m, n = map(int, input().split())
print(min(countNum(m, 5) - countNum(n, 5) - countNum(m-n, 5), countNum(m, 2) - countNum(n, 2) - countNum(m-n, 2)))