백준 11401

문제

---

이항계수를 구하는 문제

nCk = (n!) / (k!) * ((n-k)!)

팩토리얼을 계산하고, 문제는 분모의 값도 계산하고 1,000,000,007로 나누어야 한다는 점

일단 1,000,000,007은 10억을 넘는 가장 작은 소수라고 함

그렇다면 페르마의 소정리를 활용 가능

---

1,000,000,007과 서로소인 a가 있을 때

mod 1,000,000,007에서 a로 나누는 행위는 a^1,000,000,005를 곱하는 것과 같다.
(a의 역원은 a^1,000,000,005)

이 원리를 이용해 분모의 값들을 계산하고

값이 클 수 있기 때문에 long타입을 쓰고 중간중간에 1,000,000,007로 나눠주기

---

package test;

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

public class P11401 {

	static final long MOD = 1000000007;
	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 K = Long.parseLong(st.nextToken());
		
		long a = factorial(N);
		long b = factorial(K) * factorial(N - K) % MOD;
		
		long result = a * pow(b, MOD - 2) % MOD;
		
		bw.write(String.valueOf(result));
		
		br.close();
		bw.flush();
		bw.close();
	}
    
	private static long factorial(long N) {
		if(N <= 1) {
			return 1;
		}
		return N * factorial(N - 1) % MOD;
	}
    
	private static long pow(long A, long exponent) {
		if(exponent == 1) {
			return A % MOD;
		}
		
		long temp = pow(A, exponent / 2);
		
		if(exponent % 2 == 1) {
			return ((temp * temp % MOD) * (A % MOD)) % MOD;
		}
		return temp * temp % MOD;
	}
}

---

참고 :

https://st-lab.tistory.com/241