[BOJ]2004. 조합 0의 개수

문제:

nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 정수 n,m(0<=m,n<=2,000,000,000 ,n!=0)이 들어온다.

출력:

첫째 줄에 0의 개수를 출력한다.

풀이 방법:

 이와 비슷한 문제로 팩토리얼에서 0의 개수를 구하는 문제와 유사하다. 조합은 팩토리얼들의 연산들로 구할 수 있기 때문이다. 그 문제와 마찬가지로 nCm를 소인수 분해 했을 때 2의 갯수와 5의 갯수가 전체 0의 갯수와 관련있게 된다. 따라서 2와 5로 매번 나누면서 count를 하나씩 증가시켰더니 시간초과가 발생해버렸다. 아무래도 2,000,000,000 와 같이 엄청 큰 수가 들어 있는 것 같다. 

 따라서 시간초과를 해결하기 위해서 방법을 알아보는 도중에 2의 제곱수로 나눈 몫을 계속해서 더한 것이 2의 총 갯수가 된다는 것이였다. 간략히 그 이유를 설명하면 n!에 2가 들어 있는 수들은 크게 2의 배수, 4의 배수, 8의 배수....와 같이 있다고 생각할 수 있다. 예를 들어 10!이라고 가정하면 먼저 2의 배수를 세면 2, 4, 6, 8, 10이 있고 이 들의 개수를 하나씩 카운트를 증가시킬 수 있고, 그 다음에는 4의 배수는 4, 8이고 8의 배수는 8 하나이므로 총 8개의 2가 있게 된다. 표로 보면 다음과 같다.

2	3	4	5	6	7	8	9	10	계
1		1		1		1		1	5
		1				1			2
						1			1
1		3		1		3		1	8

 이와 같은 방법으로 5를 구한다음에 nCm =n! / (m! * (n-m)!) 이므로 이에 맞춰서 2의 갯수와 5의 갯수를 구한 뒤에 더 작은 값이 0의 갯수가 될 것이다.

a,b=map(int,input().split())
 
def counts(N):
    answer2=0
    answer5=0
    count=1
    while (True):
        if N//(5**count)>0:
            answer5+=N//(5**count)
            count+=1
        else:
            break
    count=1
    while (True):
        if N//(2**count)>0:
            answer2+=N//(2**count)
            count+=1
        else:
            break
    return answer2,answer5
 
a1,b1=counts(a)
a2,b2=counts(b)
a3,b3=counts(a-b)
print(min(a1-a2-a3,b1-b2-b3))