알고리즘 문제를 풀다 보면
"답이 커질 수 있으니 $1,000,000,007$로 나눈 나머지를 출력하시오"
이런 문장이 많이 보인다.
오늘은 이런 나머지연산에 대한 이야기를 하고자 한다.
이 문제를 한번 보자
단순히 문제에서 제시한대로 구현한다면 이런 코드가 나올것이다.
n = int(input())
a, b = 0, 1
for i in range(n):
a,b = b, a+b
print(a%1000000007)
하지만 이렇게 제출하게 되면 시간초과 또는 틀렸습니다를 받는다.
그 이유는 계산 과정에서 a, b의 값이 매우 커지기 때문이다.
이를 해결하기 위해 우리는 코드를 다음과 같이 수정한다.
n = int(input())
a, b = 0, 1
for i in range(n):
a,b = b, (a+b)%1000000007
print(a%1000000007)
이것이 가능한 이유는 다음과 같은 성질 때문이다.
1. $(A+B) \% M = ((A\%M)+(B\%M))\%M$
2. $(A-B) \% M = ((A\%M)-(B\%M))\%M$
3. $(AB) \% M = ((A\%M)(B\%M))\%M$
문제는 나눗셈이다.
$(A/B) \% M = ((A\%M)/(B\%M))\%M$ 는 성립하지 않는다.
만약 M이 소수라면 페르마의 소정리를 이용하여 아주 간단하게 해결할 수 있다.
$a^{p-1} \equiv 1 \pmod{p}$, 단 $p$는 소수이고 $ p \not| \ a $
페르마의 소정리에서 양변을 $a^{-1}$을 곱해주면 $a^{p-2} \equiv a^{-1} \pmod{p}$이 된다.
$(A/B) \% M = (AB^{-1})\%M = ((A\%M)(B^{-1}\%M))\%M$
에서 페르마의 소정리를 이용하면
$ ((A\%M)(B^{-1}\%M))\%M = ((A\%M)(B^{M-2}\%M))\%M$
로 모듈러의 성질을 이용할 수 있다.
증명
페르마의 소정리를 증명하는 방법에는 여러가지가 있겠지만 그 중 내가 아는 방법을 소개하려고 한다.
소수 $p$에 대해서 순열 $\{1,2,3, \dots , p-1\}$이 있다고 하자.
이 순열에 $a$를 곱할건데 $a$는 $p$와 서로소여야 한다. (그렇지 않을경우 모든 요소가 $0$이 된다.)
그럼 순열 $\{a, 2a, 3a, \dots, (p-1)a \}$를 얻는다.
이를 모듈러 $p$를 취해주면 $a$에 상관없이 순열이 된다. ($p$가 소수이기 때문)
위의 두 순열은 같은 값을 가지고 순서가 다른 순열이므로(같을 수도 있음) 모든 요소를 곱하면 같은 값을 가진다.
즉 $1 \cdot 2 \cdot \cdots \cdot (p-1) \equiv a \cdot 2a \cdot \cdots \cdot (p-1)a \mod p$
정리하면 $ (p-1)! \equiv a^{p-1}(p-1)! \mod p$이고 $(p-1)!$의 역원을 양변에 곱하면 $a^{p-1} \equiv 1 \mod p$를 얻는다. $\Box$
이 성질은 M이 소수일 때만 가능한데 문제에서 많이 나오는
$10 \ 007, \ 10 \ 009, \ 998 \ 244 \ 353, \ 1 \ 000 \ 000 \ 007, \ 1 \ 000 \ 000 \ 009$ 들은 소수이다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] 이분탐색 (0) | 2021.12.23 |
---|---|
[알고리즘] 알고리즘 문제를 풀 때 알면 좋은것들 (0) | 2021.12.05 |
[알고리즘] 피보나치 수열의 성질 (0) | 2021.12.02 |
[알고리즘] 분할 정복을 이용한 거듭제곱 (0) | 2021.12.02 |
[알고리즘] 피보나치 수 구하기 (0) | 2021.12.02 |