白駿2004/組合せ0の個数

質問する

に答える

説明:

0個の数を組み合わせる問題を解くにはまず工場0個の数を理解しなければならない.
工場0の数量
上のリンクの問題を見るとわかりますが、肝心なのは工場値の2と5の乗数が重なる数を求めることです.
工場の中で0個の数の問題を探して、2より小さい5個の数を探し出すだけでいいです.
しかし、組み合わせで求める方法は少し違います.
まず,組合せ,すなわち二項係数の式を考慮する.この項係数の式は以下の通りである.
ここで0の個数は2と5のオーバーラップ乗数、すなわちn!に等しい.(n-m)!, m!要求された2と5の勝数.
より簡単に言えば、で2の乗数(a 1−b 1,c 1)と5の乗数(a 2−b 2−c 2)を求めれば、今では重なる(ペア可能な)個数を求めることができるので、2と5の乗数のうち最大値を出力することができる.

コード#コード#

import java.util.Scanner;

public class Num2004 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long n = sc.nextInt();
		long m = sc.nextInt();
		
		// 각각 몇 제곱인지 구해준다.
		long count5 = five(n) - five(n - m) - five(m);
		long count2 = two(n) - two(n-m) - two(m);
		
		// 2와 5 중 제곱의 수가 덜나온 함수를 출력한다.
		System.out.println(Math.min(count5, count2));
	}
	//2의 제곱 수를 구하는 함수
	private static long two(long num) {
		int count = 0;
		
		while(num >= 2) {
			count += (num/2);
			num /= 2;
		}
		
		return count;
	}
	//5의 제곱 수를 구하는 함수
	private static int five(long num) {
		int count = 0;
		
		while(num >= 5) {
			count += (num / 5);
			num /= 5;
		}
		
		return count;
	}
}

注意:https://st-lab.tistory.com/166
ソース:https://www.acmicpc.net/problem/2004