수학 / 백준 2004 조합 0의 개수

 

문제 접근

n!/(n-m)!m!

각 n!, (n-m)!, m! 의 2와 5의 제곱수를 구해서 10이 몇번 만들어지는지 구함

 

2와 5의 제곱수 중 작은 값을 구함

>> 0의 개수

풀이

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

public class S2004 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());

        long cnt5 = five(n) - five(n - m) - five(m);
        long cnt2 = two(n) - two(n - m) - two(m);

        System.out.println(Math.min(cnt5, cnt2));
    }

    static long five(long num) {
        long cnt = 0;

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

    static long two(long num) {
        long cnt = 0;

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