코딩못하는사람

페르마 소정리 보안 수업에서 자주 봤던 정리이다. 여기서 한번더 나아가면 다음과 같은 식을 유도할 수 있다. 이말은 모듈러 p에 대해서 a의 역원이 a^p-2가 된다는 뜻이다. 이걸 알고 문제를 들어가야 풀 수 있다. www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 1.접근 n이 너무 크기때문에 이항계수 성질을 이용한 O(n^2)의 풀이는 불가능 할 것이라고 생각했다. 2.풀이 이 문제의 궁극적 목표인 이항계수의 식을 써보자면 N!/(N-K)!*(K)이다. 이것을 %P로 나눈값을 ..