2004.조합0의개수

문제

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

입력

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

출력

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	50057	14119	11624	28.691%

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

풀이

알고리즘 흐름

팩토리얼0의 개수 문제 처럼 2와 5의 승수가 겹치는 수를 구한다. 예를 들어 25C12 조합의 경우

25! / 13! * 12! 으로 표현될것이다. 즉 n! / (n-m)! * m! 이고 n! , (n-m)!, m! 에서 2와 5의 승수를 구하면 된다.

a1 : 2의 승수 , b : 5의 승수
n! = {2,5}(a1,b1)   ,(n-m)! = {2,5}(a2,b2)    , m! = {2,5}(a3,b3)

결과적으로,
2의 승수는 (a1 - a2 - a3) , 5의승수는 (b1-b2-b3)

이를 바탕으로 2와 5의 승수중 최소값을 출력하면 된다.

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  

public class 조합0의개수 {  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  

        String[] split = br.readLine().split(" ");  

        long n = Long.parseLong(split[0]);  
        long m = Long.parseLong(split[1]);  

        long count5 = count5(n) - count5(n-m) - count5(m);  
        long count2 = count2(n) - count2(n-m) - count2(m);  


        System.out.println(Math.min(count5,count2));  
        br.close();  

    }  

    public static int count5(long num){  
        int count = 0;  

        while (num >=5){  
            count = (int) (count + (num/5));  
            num = num/5;  
        }  
        return count;  
    }  


    public static int count2(long num){  
        int count = 0;  

        while (num >=2){  
            count = (int) (count + (num/2));  
            num = num/2;  
        }  
        return count;  
    }  
}