[BOJ] 11401. 이항 계수 3

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

출력

 (NK)를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 

5 2

예제 출력 

10

---

풀이

 

코드

import java.util.Scanner;

public class B11401 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long p = 1000000007;

        long[] fac = new long[n+ 1];
        fac[0] = 1;
        fac[1] = 1;
        //fac data 구하기
        for (int i = 2; i <=n; i++) {
            fac[i] = (fac[i - 1] * i) % p;
        }

        //분모 구하기
        long denominator = (fac[k] * fac[n-k]) % p;

        // denominatorK(분모의 K-2 제곱 구하기)
        long idx = p - 2;
        long denominatorK = 1;
        while (idx > 0) {
            //홀수이면
            if (idx % 2 == 1) {
                denominatorK *= denominator;
                denominatorK %= p;
            }
            denominator = (denominator * denominator) % p;
            idx /= 2;
        }
        long result = ((fac[n] % p) * (denominatorK % p)) % p;
        System.out.print(result);

    }
}

문제 출처 : https://www.acmicpc.net/problem/11401