https://www.acmicpc.net/problem/2004
문제
소스코드
import sys
n, m = map(int, sys.stdin.readline().split())
n_power = [0, 0]
m_power = [0, 0]
square_5 = 5
square_2 = 2
while square_5 <= n:
n_power[0] += n // square_5
m_power[0] += (m // square_5) + ((n - m) // square_5)
square_5 *= 5
while square_2 <= n:
n_power[1] += n // square_2
m_power[1] += (m // square_2) + ((n - m) // square_2)
square_2 *= 2
print(min(n_power[0] - m_power[0], n_power[1] - m_power[1]))
풀이
- 이전에 풀었던 팩토리얼 문제와 유사한 문제이다.
- 팩토리얼 문제에서 10(2 x 5)의 개수를 구하는데 5의 지수만 구하는 방법을 사용했던 것은 팩토리얼에서는 5의 지수가 2의 지수보다 작게 나오기 때문에 5의 지수만을 계산했다.
- 조합에서는 2의 지수와 5의 지수 중 어느 값이 더 작게 나올지 모르기 때문에 둘 다 계산하고 이 중 더 작은 값이 0의 개수이다.
