Baekjoon 11401 이항 계수 3 JAVA

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

11401번: 이항 계수 3

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2011401

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 N과 K이 주어졌을 때 이항계수를 구하는 문제다.

 

해당 문제에서는 페르마의 소정리라는 개념과, 모듈러 증명을 이용해서 문제를 해결했다.

​

먼저 모듈러 증명이란 ( a + b) % c == ( a%c + b%c) % c가 성립한다는 내용이다

즉 문제에서 C는 1,000,000,007이 된다.

​

nCr 을 식으로 변환하면 n! / r!(n-r)!이 되는데, n!의 경우 반복을 통해 곱해주면서 모듈러 연산을 진행하면 되지만

r!(n-r)!에 대해서는 페르마의 소정리를 이용하여아한다.

해당 부분은 분모이기 때문에 페르마의 소 정리를 통해 r!(n-r)! ^ 1,000,000,007-2를 해주면 된다.

최종 식은 N! * (R!(N-R)!) ^ 1,000,000,005가 되며 계산식을 하면서 모듈러 증명일

해주어야 한다.