백준 / 조합 0의 개수 / 2004

Question

문제링크
Silver 2

문제

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

Input

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

25 12

Output

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

2

Logic

기본 구조 : while문
1. 어떤 수 n에 대해 n!가 key라는 수를 얼마나 가지고 있는지 세는 함수를 만든다.
2. 2와 5 각각에 대해 n에 포함된 갯수에서 m에 포함된 갯수, n-m에 포함된 갯수를 제한다.

Code

n, m = map(int, input().split())

def count(key,n):
    num = 0
    while n != 0:
        n = n // key
        num += n
    return num
    
print(min(count(5,n)-count(5,n-m)-count(5,m),count(2,n)-count(2,n-m)-count(2,m)))