11401 이항계수3 (페르마 소정리)

페르마 소정리

보안 수업에서 자주 봤던 정리이다.

 

여기서 한번더 나아가면

다음과 같은 식을 유도할 수 있다.

 

 

이말은 모듈러 p에 대해서 a의 역원이 a^p-2가 된다는 뜻이다.

 이걸 알고 문제를 들어가야 풀 수 있다.

 

www.acmicpc.net/problem/11401

11401번: 이항 계수 3

1.접근

n이 너무 크기때문에

이항계수 성질을 이용한 O(n^2)의 풀이는 불가능 할 것이라고 생각했다.

 

 

2.풀이

이 문제의 궁극적 목표인 이항계수의 식을 써보자면 N!/(N-K)!*(K)이다. 이것을 %P로 나눈값을 찾아야한다.

 

하지만 기본적으로 모듈러 연산에 대한 분배법칙은 곱셈,덧셈,뺄셈에 대해서만 성립되고 나눗셈에 대해서는 성립되지 않는다.

 

따라서 우리는 분모를 어떻게 해결할 것인지를 고민해야 한다.

 

 

 

 

따라서 우리는 위에서 정리한 페르마 소정리를 이용하여 분자 분모에 (N-K)!*(K)에 모듈러P에 대한 역원을 곱해줘서 분모를 1 로 만들 수 있다. 역원은 (N-K)!*(K)^(p-2)이될것이다.

 

이에 따라 우리는 N! * (N-K)!*(K)^(p-2)을 구해주는 문제로 바뀐 것이다.

 

팩토리얼을 시간N에 해결하고 거듭제곱을 log시간에 해결할 수 있다.

나는 조합의 계산의 특성을 이용해서 5C2라고 하면 5*4/2*1 같이 약분해서 좀더 간단하게 계산했다.

3.코드

4.배운점

• 이 문제는 확장 유클리드로도 풀 수 있다.
• N이 클때 모듈러 연산에서 dp로 팩토리얼을 구하니 메모리를 너무 많이 잡아먹었다.
• 거듭제곱을 처리할 때 분할정복을 이용해서 푸는 방법과 while 문을 써서 푸는 방법 둘다 알자.
• 두달만에 풀어서 좋다 

 

www.acmicpc.net/board/view/15795를 보고 도움을 얻었습니다.