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

 일반적인 이항계수 공식으로는 시간초과및 오버플로우가 나와버린다.

그도 그럴것이 문제에서는 최악의 경우 4000000!을 계산하고 그래야하는데

이것은 long타입의 저장범위를 아득히 넘어버린다. 

 

 그로 인해 우리는 다른 방법을 생각해 보아야 하는데 여기서 나오는것이 페르마의 소정리이다.

우리는 알고리즘 문제를 푸는것이지 수학문제를 푸는것이 아니기 때문에 간략하게 정리만 하고 넘어갈것이다.모듈러연산(페르마의 소정리)의 공식에는 덧셈,뺄셈,곱셈이 있으면 나눗셈은 통용되지 않는다.

 

우선 페르마의 정의는 이렇다.

페르마의 소정리

여기서 조금만 더 나아간다면

페르마의 보조공식

이렇게 유도가 가능할 것이다. 

그렇다면 우리가 구하고 싶은 나눗셈 꼴은 역원으로 구할수있으면 이를 정리하면

위와 같이 나오며 최종적으로 우리가 도출하고자 하는 계산식은 아래와 같다

즉 제곱승을 해주는 메소드를 하나 더 작성하면 된다.

 

import java.io.*;

import java.util.StringTokenizer;

public class Main {
    final static long p = 1000000007;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        long N = Long.parseLong(st.nextToken());
        long K = Long.parseLong(st.nextToken());

        long number = factorial(N);
        long denom = factorial(K) * factorial(N-K) % p;

        System.out.println(number * pow(denom, p-2) % p);

    }

    public static long factorial(long n){
        long result = 1L;
        while(n>0){
            result *= n;
            result %= p;
            n--;
        }
        return result;
    }

    public static long pow(long base, long expo){
        long result = 1;
        while(expo > 0){
            if (expo%2 == 1) {
                result *= base;
                result %=p;
            }
            base = base * base;
            base %= p;
            expo /= 2;
        }
        return result;
    }
}