116. 2004(조합 0의 개수)

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

class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sBits = br.readLine().split(" ");
		int n = Integer.parseInt(sBits[0]);
		int m = Integer.parseInt(sBits[1]);
		
		int five = fiveCnt(n)-fiveCnt(n-m)-fiveCnt(m);
		int two = twoCnt(n)-twoCnt(n-m)-twoCnt(m);
				
		System.out.println(Math.min(five, two));

	}

	public static int fiveCnt(int x) {
		int cnt = 0;
		while (x >= 5) {
			cnt += x / 5;
			x /= 5;
		}
		return cnt;
	}

	public static int twoCnt(int x) {
		int cnt = 0;
		while (x >= 2) {
			cnt += x / 2;
			x /= 2;
		}
		return cnt;
	}
}

문제요약

이항계수를 구한 값에서 뒤부터 0이 아닌 숫자가 나올 때까지 0은 몇번 나오는가?

설명

이 문제는 조합을 먼저 구하고 할 수 없다.

조건이

최대 입력값이 20억이기 때문에 규칙을 찾아야 한다.

이항계수는 다음과 같이 식을 표현 할 수 있다.

 

뒤에 0이 나오는 경우는 2 * 5를 가지고 있는 수이며, 2가 a승 5가 b 승일 때 a와 b 중 더 작은 값이 0의 개수이다.

 

따라서 n!과 n-r!과 r!의 2의 승수, 5의 승수를 구하고, 각 값들을 빼준다.

그리고 그 값에서 2의 승수, 5의 승수 중 더 작은 값이 0의 개수가 된다.

 

 승수를 빼주는 이유는

 다음과 같기 때문이다.