모듈러 연산 정리와 이항계수 문제 풀이

#1 이항계수 정의

이항계수란 고등학교때 확률과 통계에서 배웠던 조합 공식이다.

 

팩토리얼과 나눗셈으로 이루어져 있기 때문에 이와 모듈러 연산을 결합하여 알고리즘 문제를 만드는 백준 '이항계수 3' 과 같은 문제가 있어 정리하게 되었다.

 

#2 모듈러 연산

모듈러 연산의 경우 덧셈과 곱셈에서는 분배 법칙이 적용 가능하다. 식은 다음과 같다.

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

 

그러나 나눗셈에서는 불가능한데,

모듈러 연산이 핵심인 알고리즘 문제의 경우 분배법칙을 적용하지 않으면 숫자가 너무 커지도록 설계를 해두는 경우가 있어서 정리하게 되었다.

 

#3 페르마의 소정리

페르마의 소정리란, a가 정수이고 p가 소수일 때,

위 식을 만족한다는 것이다.

따라서 a^(p-1) 에 나머지 연산을 취한 값이 1이 된다. 이에 따른 식을 변형해주면 아래와 같이 나눗셈에 모듈러 연산을 사용할 수 있는 경우가 생기게  된다.

이를 power와 반복문을 사용해서 그대로 계산해주는 코드를 작성하면 된다.