✓

태그:

16. 정수론 및 조합론

_nC_m의 뒤부터 연속하여 나타나는 0의 개수를 출력하는 문제입니다. 우선 수 뒤에 0이 n개 붙는 것은 소인수분해했을 때 2^k×5^l이 포함되어있을 때, k와 l중 작은 값이 n이 된다는 것입니다.(1676번: 팩토리얼 0의 개수 참조) 그래서 우리가 해야 하는 것은 _nC_m을 소인수분해했을 때 2와 5의 지수가 몇이 되는가를 알아내는 것입니다.

_nC_m은 정의 상 \(\frac{n!}{m!(n-m)!}\)입니다. 1676번: 팩토리얼 0의 개수 문제에서 n!을 소인수분해했을 때 5의 지수를 구하는 방법을 설명했는데, 이것을 응용하여 풀어보겠습니다. 우선 1676번 문제에 의해 n!의 2의 지수는 \([\frac{n}{2}]+[\frac{n}{4}]+[\frac{n}{8}]+...\)이고 5의 지수는 \([\frac{n}{5}]+[\frac{n}{25}]+...\)이었습니다. 그런데 위의 식과 같이 조합을 정의하므로 n!의 지수를 구한 후 m!의 지수와 (n-m)!의 지수를 빼주면 _nC_m를 소인수분해했을 때 나오는 2의 지수와 5의 지수를 구할 수 있을 것입니다. _nC_m의 2의 지수와 5의 지수를 구했다면, 둘 중 작은 것을 출력하면 됩니다.

소스 코드

언어	코드	시간
Python 3	코드(Github) / 코드(백준)	2020-04-02 19:03:13

---