조합 0의 개수

문제

풀이

이 문제의 핵심은 팩토리얼에서 소인수분해를 하는 것이다.
물론 소인수분해를 다 하는 것이 아니다.
우리가 필요한 것은 2, 5뿐이다.

ex) 25! => 2의 지수는?
답은 12+6+3+1 = 22이다.

2가 포함된 수 => 2,4,6,8,10,12,14,16,18,20,22,24 = 12개
4가 포함된 수 => 4,8,12,16,20,24 = 6개
8이 포함된 수 => 8,16,24 = 3개
16이 포함된 수 => 16 = 1개이다.

이제 조합(combination)공식을 이용하면
25!/12!13! 이다.

이것을 코드로 나타내면 다음과 같다.