수학 - 페르마의 소정리를 이용한 나눗셈에 대한 MOD 연산

PS를 하다보면 1,000,000,007와 같이 소수로 나눈 나머지를 출력하라는 경우가 많다. 문제는 계산 과정에 나눗셈이 들어가는 답안의 경우 무턱대고 나눈 뒤 mod 연산을 하면 틀렸습니다!를 받기 쉽다는 것이다. 이를 해결하기 위해서는 페르마의 소정리를 이용하면 된다.

 

페르마의 소정리는 다음과 같다.

p가 소수이고 a가 p의 배수가 아니면 a^(p-1) ≡ 1 (mod p)이다.

즉, a^(p-1) mod p = 1이다.

 

위의 식을 살짝 바꾸면 다음과 같이 변한다.

a^(p-2) ≡ a^-1 (mod p)

즉, a로 나누고 mod p하는 것은 a^(p-2)를 곱하고 mod p하는 것과 같다는 것이다. 물론! a^(p-2)를 구하는 과정에서도 mod 연산을 해줘야 할 것이다. 

 

어라? 그런데 문제에서 p를 1,000,000,007 같이 무지막지한 수로 주는데 그러면 a^1,000,000,005 구하는데도 시간이 너무 오래 걸리지 않나요?

그럴때는 아래 글을 참조하면 된다. 분할정복으로 아주 빠르게 거듭제곱을 할 수 있기 때문이다.

수학 - 거듭제곱

 

따라서 앞으로  "n / a % 1,000,000,007" 해서 틀렸습니다! 받지 말고, "n * (a ^1,000,000,005) % 1,000,000,007"해서 맞았습니다!를 받아보자.