백준 : 11401

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

11401번: 이항 계수 3

페르마의 소정리와 확장 유클리드 알고리즘으로 값구하기.

확장 유클리드알고리즘은 Ax + By = GCD(A,B) 라고할때 맞는 정수 x y를 구하는 방법이다.

재귀 적인 방법이 있고 반복문을 통한 반복이 있는 반복문을 통한방법이 이해하기 쉬우므로 사용하였다.

아래는 재귀적으로 푸신분의 소스참조.. 이해할려고해도 이해잘안됨 

https://onsil-thegreenhouse.github.io/programming/problem/2018/04/02/problem_combination/

[Problem] 이항계수 구하기(백준 11401번) - Onsil's blog

package day0301;
 
import java.util.Scanner;
 
public class B11401 {
static long p = 1000000007L;
    static long Uclede(long a, long b) {
        // Ax + By = 1 만족하는거 찾기
        long s[] = new long[2];
        long t[] = new long[2];
        s[0] = 1; t[0] =0;
        s[1] = 0; t[1] = 1;
        
        while(a %b != 0) {
            long ss = s[0] - (a/b)*s[1];
            long tt = t[0] - (a/b)*t[1];
            
            s[0] = s[1];
            t[0] = t[1];
            
            s[1] = ss;
            t[1] = tt;
            
            long tmp = b;
            b = a%b;
            a = tmp;
            
        }
        return t[1] = t[1] < 0 ? t[1] +p : t[1];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int K = sc.nextInt();
        
        
        long factor[] = new long[N+1];
        factor[1] = 1;
        
        for(int n=2;n<=N;n++) {
            factor[n] = (n * factor[n-1]) % p;
        }
        //result = N! * x % p --> x : (N-K)!K! x + P y = 1 만족하는 x
        if(N==1 || K==0||K==N) {
            System.out.println(1);
        }else {
            
            long x = Uclede(p, (factor[N-K] * factor[K])%p);
            
            long result = (factor[N]*x)%p;
            
            System.out.println(result);
        }
        
        
        
    }
}