조합 0의 개수 풀이

문제 링크: https://www.acmicpc.net/problem/2004

백준 정수론 및 조합론 12단계 - 2004번 조합 0의 개수를 풀어보았다.

 

풀이: 팩토리얼 0의 개수 문제와 비슷하다. 5와 2의 개수를 세면 되는데, a! 에서 b가 몇 번 나타나는지 알고 싶으면 a//b를 하면 된다는 것을 알게 되었다.

 

C++

 

Python

def count(a,b):
	cnt=0
	while a:
		a//=b
		cnt+=a
	return cnt

n,m=map(int,input().split())
fives=count(n,5)-count(m,5)-count(n-m,5)
twos=count(n,2)-count(m,2)-count(n-m,2)
print(min(fives,twos))

Java