[Java/자바][백준 2004: 조합 0의 개수]

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

2004번: 조합 0의 개수

Problem

nCm 의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

 

Input 

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

 

Output

첫째 줄에 nCm의 끝자리 0의 개수를 출력한다.

 

Insight

1. 팩토리얼 0의 개수 게시물을 참고할 것! 

https://yu1moo.tistory.com/entry/Java백준-1676-팩토리얼-0의-개수

[Java][백준 1676: 팩토리얼 0의 개수]

2. nCr =  n! /   r! * (n-r) !

3. 0의 개수는 2와 5의 개수로 정해진다 -> 2의 개수와 5의 개수 중에 더 작은 빈도수를 가진 개수가 0의 개수가 된다.

 

<Process> 
1. 조합의 2의 빈도수와 5의 빈도수를 각각 구한다. 
2. nCr은 나눗셈의 형태를 가지고 있기 때문에 n!의 2의 개수에서 (n-r)! 의 2의 개수와 r! 의 2의 개수를 빼줘야 한다. (5도 동일)
3. 2의 빈도수와 5의 빈도수 중 작은 값을 가지고 있는 값을 출력

 

import java.util.*;
import java.io.*; 

public class Main {
    
    public static void main(String[] args) throws IOException{ 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());
        
        Long two=0L, five=0L; 
        two = zero_cnt(n,2) - zero_cnt(n-m,2) - zero_cnt(m,2);
        five = zero_cnt(n,5) - zero_cnt(n-m,5) - zero_cnt(m,5);
        
        bw.write(String.valueOf(Math.min(two,five)));
        
        bw.flush();
        bw.close();
    }
    
    public static long zero_cnt(long input, long k){
        long cnt=0; 
        for(long i=k; i<=input; i*=k){
            cnt += input/i; 
        }
        return cnt; 
    }
}