백준 11401 이항 계수 3

문제

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

---

코드

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

public class Main {
    public static long factorial(int n){
        long result=1L;
        while(n>1){
            result=result*n%1000000007;
            n--;
        }

        return result;
    }

    public static long recursive(long base, int exponentiation){
        if(exponentiation==1)
            return base%1000000007;

        long temp=base*base%1000000007;
        if(exponentiation%2==1)
            return base*recursive(temp, exponentiation/2)%1000000007;
        else
            return recursive(temp, exponentiation/2)%1000000007;
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s=br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        long result=factorial(k)*factorial(n-k)%1000000007;
        result=recursive(result, 1000000005);
        result=factorial(n)*result%1000000007;

        bw.write(result + "\n");
        bw.flush();
    }
}

---

해결 과정

1. 이항 계수는 알고 있었지만 페르마의 소정리를 몰라서 어려웠다. mod 연산과 페르마의 소정리에 대해서 공부하고 난 뒤에 수학적으로 문제를 풀었다. 그것을 토대로 Recursive로 factorial을 구현하고 Math.pow 메소드를 사용해서 문제를 풀었다.

2. 틀렸습니다(long의 범위를 한참 뛰어 넘어서 잘못된 연산. 하지만 수학적으로 틀린 줄 알고 긴 시간 동안 다시 페르마의 소정리를 공부하면서 삽질 했다, 반복문으로 factorial을 구현하고 pow 연산을 분할정복으로 구현하면서 계속 %연산을 해줬다)

3. 😁