116. 2004(조합 0의 개수)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())


def fiveCnt(x):
    cnt = 0
    while x >= 5:
        cnt += x//5
        x //= 5
    return cnt


def twoCnt(x):
    cnt = 0
    while x >= 2:
        cnt += x//2
        x //= 2
    return cnt


print(min(fiveCnt(n)-fiveCnt(n-m)-fiveCnt(m), twoCnt(n)-twoCnt(n-m)-twoCnt(m)))

문제요약

이항계수를 구한 값에서 뒤부터 0이 아닌 숫자가 나올 때까지 0은 몇번 나오는가?

설명

이 문제는 조합을 먼저 구하고 할 수 없다.

조건이

최대 입력값이 20억이기 때문에 규칙을 찾아야 한다.

이항계수는 다음과 같이 식을 표현 할 수 있다.

 

뒤에 0이 나오는 경우는 2 * 5를 가지고 있는 수이며, 2가 a승 5가 b 승일 때 a와 b 중 더 작은 값이 0의 개수이다.

 

따라서 n!과 n-r!과 r!의 2의 승수, 5의 승수를 구하고, 각 값들을 빼준다.

그리고 그 값에서 2의 승수, 5의 승수 중 더 작은 값이 0의 개수가 된다.

 

 승수를 빼주는 이유는

 다음과 같기 때문이다.