2004_조합 0의개수

문제는 더보기!

 

조합 0의 개수 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

29521

8232

6864

28.938%

문제

 (nm)$n \choose m$의 끝자리 0$0$의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n$n$, m$m$ (0≤m≤n≤2,000,000,000$0 \le m \le n \le 2,000,000,000$, n≠0$n \ne 0$)이 들어온다.

출력

첫째 줄에 (nm)$n \choose m$의 끝자리 0$0$의 개수를 출력한다.

예제 입력 1 복사

25 12

예제 출력 1 복사

2

 

 

이전 문제와 상당히 유사한데 이항계수의 식을 먼저 보자.

 

 

10을 만드려면 2 * 5가 나와야한다. 즉 위 식을 계산했을때 2 * 5가 몇개있는지 구해주면 되는 문제이다.

 

즉, 저식을 계산한값중 2의개수와 5의개수를 구해서 둘중 작은값이 뒤에붙은 0의 개수가 된다!

 

 

이때 5의 개수를 구한다면 그저 5로 나눈값을 구하면 안된다. 25의 경우 5*5이기때문에 5가 2개 들어오기 때문!

 

 

24! = 1 * 2 * 3 * ... * 24    >> 5가 5,10,15,20일때 총 4개

25! = 1 * 2 * 3 * ... * 25    >> 5가 5,10,15,20,25(5*5) 일때 총 6개 가들어오게된다.

 

 

 

n,k = map(int,input().split())
lst=[1,1]
for a in range(2,200):
    lst.append(lst[-1]*a)

    count = 0
    for i in reversed(str(lst[-1])):
        if i == '0':
            count += 1
        else:
            break
    print( a, ':', count )

print( lst[n] // ( lst[k] * (lst[n-k])))

위코드를 한번 돌려보면 5의 개수가 어떻게 늘어나는지 볼 수 있다. 입력으로 아무숫자 2개를 5 3 이렇게 넣으면 된다.

 

 

나머지는 위에서 설명했던 방식으로 해결했다!

n,m = map(int,input().split())
five = [ 5**x for x in range(1,14)]
two =  [ 2**x for x in range(1,31)]

def get_five(num):
    count = 0
    for i in five:
        count += num // i
    return count

def get_two(num) :
    count = 0
    for i in two:
        count += num // i
    return count

print( min( get_five(n) - get_five(m) - get_five(n-m)  , get_two(n) - get_two(m) - get_two(n-m) )  )