[백준]2004 조합0의 개수 #팩토리얼#나누기

1. 풀이

nCm의 뒤에 0의 개수는 10이 곱해준 수와 같다. 따라서 nCm=n!/(m! * (n-m)!) 에서 10이 몇번곱해졌는지를 확인한다.

(1) 10이 몇번곱해졌는지 알기위해선 소인수분해를 이용해 2와 5가 몇번곱해졌는지를 확인한다.

(2) n!에서 num가 몇번곱해졌는지는 다음의 방법으로 알 수가 있다.

ex) 150! 에서 5가 몇번곱해졌는가?

5^1이 곱해진 횟수를 구한다 => 150//5=30

5^2이 곱해진 횟수를 구한다 => 150//25=6

5^3이 곱해진 횟수를 구한다 => 150//125=1

총 횟수 => 36

이를 소스코드로 나타내면 다음과 같다

def cntNum(a,num):
    ans=0
    multiNum=num
    while(multiNum<=a):
        ans+=a//multiNum
        multiNum*=num
    return ans

 

2. 소스코드

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

def cntNum(a,num):
    ans=0
    multiNum=num
    while(multiNum<=a):
        ans+=a//multiNum
        multiNum*=num
    return ans

a=cntNum(n,5)
b=cntNum(m,5)
c=cntNum(n-m,5)
five=a-b-c

a=cntNum(n,2)
b=cntNum(m,2)
c=cntNum(n-m,2)
two=a-b-c

print(min(five,two))