정수론을 활용하는 문제??
팩토리얼의 공식을 생각해 봅시다.
\dbinom{n}{r} = \dfrac {n!}{(n-r)!\;r!}
수가 커질수록 팩토리얼을 계산하기가 어려워짐.
따라서 다른 방향을 생각해 봐야 함.
0의 갯수 : 10이 얼마나 곱해졌는지 생각.
10 = 2 \times 5 이므로,
2가 몇 번 나눠지는지 구하고,
5가 몇 번 나눠지는지 구한뒤,
그 중 작은 것을 선택하면 됨.
- 왜 작은 것을 골라야 하는가? 10은 2와 5가 같이 있어야 만들어지기 때문에
python
"""조합 0의 갯수"""
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
def cnt(a, b):
count = 0
while a:
a //= b
count += a
return count
count2 = cnt(n, 2) - cnt(n-m, 2) - cnt(m, 2)
count5 = cnt(n, 5) - cnt(n-m, 5) - cnt(m, 5)
print(min(count2, count5))