내 인생 이대로 ㅈ될 수 없다

https://www.acmicpc.net/problem/2004

막무가내로 풀면 무조건 시간초과 메모리초과가 난다.

쓸수있는 방법을 다 써보다 안돼서 앞서 1676번에서 봤던 깔끔한 코드를 이용해보기로 했다.

https://playedenough.tistory.com/55?category=1050629 

간단하게 설명을 하자면,

만약 어떤 수 N이 0을 포함하고 있다면 그 형태는 반드시

10^N X A 일것이다.

근데 10^N을 인수분해하게 되면 2^N X 5^N 의 형태이다. 그런데 A안에도 2나 5가 포함 되어질 수도 있어서

2^N X 5^N X A 의 형태가 2^N X 5^(N+K) X A 혹은 2^(N+K) X 5^N X A 의 형태로 나타내 질 수도 있다.   

예를들어서

1320 = 13200 = 132 X 10^2 = 132 X (2^2 X 5^2) 형태를 띄게 된다.

근데 여기서 132을 인수분해하면 132 = 66 X 2 = 33 X 2 X 2 = 3 X 2^2 X 11 이므로

최종적으로는 3 X 11 X (2^4 X 5^2) 형태를 띄게 된다.

그렇기에 우리는 2와 5의 지수중에 최소값을 선택하면 그게 곧 10의 개수이고 이는 곧 0의 개수라고 생각할 수 있다.

13200 = 3 X 11 X (2^4 X 5^2) -> min(2의지수,5의지수) = 2 13200 에서 0의 개수는 2개.

이를 생각해냈다면 그 다음부터는 단순히 nCr 조합 공식을 사용하면된다.

예를들어서

25C12 를 구한다고하면

25! / (25-12)! * 12! 이다.

25 ! = ( 1 x 2 x 3 x 4 x ....... 21 x 22 x 23 x 24 x 25) 

(25-12) ! = (1 x 2 x ................ x 11 x 12 x 13)

12 ! = ( 1 x 2 x ....................... x 11 x 12)

이다.

2와 5의 개수는 def count를 통해서 쉽게 알 수 있다.

근데 여기서 주의해야할게 100! 과 같은 경우에 5의 개수를 구해보면

5의 배수에서 하나씩  (5,10,15....100) 총 20개

5^2의 배수에서는 하나씩 더  (25, 50, 75,100) 총 4개를 더 가지고 있다.

숫자가 더 커지게 되어서 5^n의 배수일때도 고려해줘야 된다.

n!에서 5의 지수승의 총합 = n/5 + n/25 + n/75 + ...... 이런 형태를 띄게된다.

이는 2의 배수에서도 마찬 가지임을 주의해야한다.

또 여기서 a-(a-b)-b 를 하는 이유는 나누기 때문이다.

엄밀히 말하면 (a-{(a-b)+b)} 이다. 

예를들어서 120/2x12를 한다고 하면 에서 2의 개수는

120 / 24 = 5

120 = 12 x 10 = 2^2 x 3 x 2 x 5 = 2^3 x 3 x 5

2x12 = 2^1 x 2^2 x 3 = 2^3 x 3

2^3 x 3 x 5 / 2^3 x 3 

= 5

2^2 / 2 = 2^2-1 = 2^1 이렇게 나타낼 수 있으니까라고 생각하면 된다.