백준 2004번 조합 0의 개수

정보

문제 바로가기 [클릭]

난이도: Silver2

관련 개념: #수학 #정수론

---

조건

시간 제한	메모리 제한
2 초	128 MB

---

문제

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

25 12

출력

2

---

코드(파이썬)

def get_fatorial_decimal(num):
    r = list()
    
    for tmp in [2, 5]:
        i = tmp
        cnt = 0
        
        while i <= num:
            cnt += num // i
            i *= tmp
        
        r.append(cnt)
            
    return r

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

result = get_fatorial_decimal(n)

for two, five in [get_fatorial_decimal(i) for i in (m, n-m)]:
    result = (result[0]-two, result[1]-five)

print(min(result))

---

특이사항

• 풀이과정
  • $n!$에서 소인수분해 시 2의 개수($n1$)와 5의 개수($n2$) 계산
  • $n! = 2^{n1} \times 5^{n2} \times …$
  • $m! = 2^{m1} \times 5^{m2} \times …$
  • $k! = 2^{k1} \times 5^{k2} \times … \quad (k = n - m)$ 라고 할 때,
  • ${n \choose {m}} \ = \frac{n!}{m! \times k!} $
    $\qquad = \frac{2^{n1} \times 5^{n2} \times …}{(2^{m1} \times 5^{m2} \times …) \times (2^{k1} \times 5^{k2} \times …)} $
    $\qquad = 2^{n1-m1-k1} \times 5^{n2-m2-k2} \times … $
    $\qquad = 10^{min(n1-m1-k1, \ n2-m2-k2)} \times … $
  • 따라서, $n \choose m$의 0의 개수는 $n1-m1-k1$과 $n2-m2-k2$ 중 작은 수에 따라 결정

---

참고문헌

-