[백준]이항 계수3/11041 풀이 JAVA

문제

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

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

 

출력

 (NK)를 1,000,000,007로 나눈 나머지를 출력한다.

 

풀이(JAVA)

모듈러 연산과 페르마 소정리를 이용해서 푸는 문제였다.

---

ㅡㅡ이렇게 완전 깊고깊은 수학 공식을 알아야하는 문제 개싫음 그냥 식을 제공해줬으면 함

처음에는 메모이제이션으로 풀었다가 숫자가 너무 커서 시간초과 걸림...

메모이제이션이 내가 젤 잘하는 건데......................

 

모듈러랑 무슨...페르마 소정리!??!! 참내....

근데 이렇게 푸니까 시간도 빠르게 걸리고 용량도 덜 차지함ㄷ

...다양한 풀이법을 알고 있어야 겠다.