[백준 11401] 이항 계수 3

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

 

 

페르마의 정리.. 를 이용하는 문제

 

A^p 

A

는 (mod p)에 대하여 동치이다(p로 나누었을 때 같은 나머지 값을 가짐)

라는 정리를 이용함. 

 

 

나머지 연산의 분배 법칙은 분모에 대하여 적용되지 않기 때문에 역원을 이용하여 위와 같은 변환을 함.

 

 

 

또한 분할정복을 이용한 거듭제곱 연산 과정을 통하여 시간복잡도를 O(logN) 으로 하여 계산하여 줌.

https://blog.naver.com/raylee00/222198946198

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int P = 1000000007;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line = br.readLine();

        int N = Integer.valueOf(line.split(" ")[0]);
        int K = Integer.valueOf(line.split(" ")[1]);

        long a = factorial(N);
        long b = factorial(K) * factorial(N - K) % P;

        long sum = a * f_pow(b, P - 2) % P;
        System.out.println(sum);

    }

    private static long factorial(int num) {
        long sum = 1;
        for (int i = num; i > 1; i--) {
            sum = sum * i % P;
        }
        return sum;
    }

    private static long f_pow(long a, long b) {
        if(b==0) return 1;
        if(b%2==1) return f_pow(a, b - 1) * a % P;
        long sum = f_pow(a, b / 2) % P;
        return sum * sum % P;
    }
}

 

 

---

https://velog.io/@gaeunek/backjoon-311401

[백준] 이항 계수 3(11401)

 

https://aruz.tistory.com/19

나머지 연산 곱셈 역원