Modular Arithmetic

모듈러 연산은 수학에서 나머지 연산을 가리키는 말입니다. 이런 분야를 정수론이라고 하는데 컴퓨터에서 실수보다 정수를 다루는 게 훨씬 자연스럽기 때문에 정수론에 대해서도 잘 알아두어야 합니다. 이 글에서는 모든 정수론의 기본이 되는 모듈러 연산에 대해서 알아봅니다. 이 내용만 문제로 출제될 정도는 아니고 다른 문제에 기본으로 들어가는 내용이기 때문에 앞으로 많이 보게 될 것입니다.

어떤 정수를 2 이상의 정수 \( n \)으로 나눴을 때 나머지는 \( [0, n - 1] \) 범위의 정수 중 하나입니다. 만약 두 정수 \( a, b \)의 \( n \)으로 나눴을 때의 나머지가 \( r \)로 같았다면 \( n \)에 대하여 합동이라고 합니다(congruent modulo \( n \)).

종종 문제에서 답이 너무 커지는 경우, 어떤 수로 나눈 나머지를 대신 구하라고 요구합니다. 예를 들어, \( n! \)을 출력하라는 문제인 경우 \( n \)이 13만 되어도 32비트 정수 범위를 벗어납니다. 그래서 \( n! \)을 그대로 구하는 것이 아닌 어떤 정수로 나눈 나머지를 구하도록 요구합니다. 여기서 어떤 수는 대부분 1,000,000,007(1e9 + 7)입니다. 저 수는 32비트 정수의 최대 크기에 가까운 소수이기 때문에 널리 사용됩니다. 지금은 별로 중요하지 않지만 나중에 저 수가 소수임이 굉장히 중요합니다.

덧셈에서의 모듈러 연산

예를 들어 정수 \( N \,\, (1 \leq N \leq 1,000,000) \)가 주어지고 \( N \)번째 피보나치 수를 찾는 문제가 있다고 해 봅시다. 참고로 피보나치 수는 0, 1, 1, 2 ... 처럼 이전 두 항을 더한 수열입니다. 하지만 \( N \)의 범위가 꽤 크고 피보나치수는 점점 기하급수적으로 커지기 때문에 64비트 정수가 표현할 수 있는 범위를 벗어납니다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    long long fibo[n + 1];
    fibo[0] = 0; fibo[1] = 1;
    for (int i = 2; i <= n; i++)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

    cout << fibo[n];
}

위 코드는 다이나믹 프로그래밍(Dynamic Programming, DP)이라는 기법을 사용해 작성되었습니다. DP에 대해서는 다른 글에서 자세히 살펴봅니다. 이 코드의 시간복잡도는 \( O(N) \)인 반면, 재귀로 만들어진 피보나치 함수는 \( O(2^N) \)이기 때문에 \( N \)이 커지면 굉장히 오랜 시간이 걸립니다.

위 코드의 문제점은 무엇일까요? \( n \)에 100을 입력해 봅시다. 100번째 피보나치 수는 3,736,710,778,780,434,371으로 굉장히 큰 숫자입니다. 200을 넣으면 -1,123,705,814,761,610,347으로 벌써 오버플로우가 발생했습니다. 오버플로우가 생겨서 음수가 되고, 음수끼리 더해서 언더플로우가 나서 다시 양수가 되기를 반복하면서 틀린 답을 내게 됩니다. 참고로 파이썬에서는 아무런 문제가 없습니다(!). 파이썬은 숫자의 범위가 사실상 무한대이기 때문에 저런 코드도 문제없이 돌릴 수 있습니다.

100만번째 피보나치 수는 208,988자리의 엄청나게 큰 수입니다. Python에서는 변수의 크기가 고정되어 있지 않아서 큰 수도 문제없이 저장할 수 있습니다. C++에서는 큰 수를 직접 저장할 수 없고 벡터를 이용해 직접 구현해야 합니다.

그래서 큰 수를 범위 안에서 처리하기 위해 나머지를 구하도록 요구합니다. 위 코드를 \( n \)번째 피보나치 수를 1e9 + 7로 나눈 나머지를 구하도록 바꿔보겠습니다.

근데 한가지 문제가 있습니다. \( n \)번째 피보나치 수를 구한 뒤 나머지를 구하려고 했는데, 이미 \( n \)번째 피보나치 수가 너무 커서 오버플로우가 났습니다. 잘못된 값의 나머지를 구해봐야 잘못된 값일 뿐입니다. 따라서 오버플로우가 생기기 전에 나머지를 구해야 합니다. 이것을 가능하게 해주는 것이 모듈러 연산의 성질입니다.

\[ (a + b) \,\%\, n = ((a \, \%\, n) + (b \,\%\, n)) \, \%\, n \]

증명

\[ \begin{align*} a &= p_1n + q_1 \\ b &= p_2n + q_2 \\ a + b &= (p_1 + p_2)n + (q_1 + q_2) \\ (a + b) \bmod n &= (q_1 + q_2) \bmod n \\ &= ((a \bmod n) + (b \bmod n)) \bmod n \end{align*} \]

이 성질은 두 수 \( a, b \)를 더하고 나머지를 구하는 것과 각각 나머지를 구한 뒤 더하고 나머지를 구하는 것이 같다는 뜻입니다. 즉, \( a + b \)가 너무 큰 경우 \( a \)와 \( b \) 각각에 나머지를 구해 크기를 줄이고 더한 뒤 나머지를 구해도 같은 결과를 얻는다는 뜻입니다. 32비트 정수의 최대 크기는 21억 정도이기 때문에 1e9 + 7 정도의 수를 더해도 오버플로우가 나지 않습니다. 이 내용을 이용해 코드를 고쳐봅시다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    const int MOD = 1e9 + 7;
    int n;
    cin >> n;

    int fibo[n + 1];
    fibo[0] = 0; fibo[1] = 1;
    for (int i = 2; i <= n; i++)
        fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD;

    cout << fibo[n];
}

여기서 fibo[i - 1]과 fibo[i - 2]를 MOD로 나누어주지는 않았는데, 전부 1e9 + 7보다 작은 값임을 알고 있기 때문에 서로 더해도 32비트 정수를 벗어나지 않기 때문입니다.

곱셈에서의 모듈러 연산

이 특성은 곱셈에서도 동일하게 성립합니다. 다만, 곱셈 특성상 나머지끼리 곱해도 32비트 정수 범위를 벗어날 수 있기 때문에 주의해야 합니다. long long 타입의 최대 크기가 \( 9 \times 10^{18} \) 정도이기 때문에 1e9 + 7로 나눈 나머지끼리 곱해도 long long 범위를 벗어나지 않습니다.

\[ ab \,\%\, n = (a \,\%\, n)(b \,\%\, n) \,\%\, n \]

증명

\[ \begin{align*} a &= p_1n + q_1 \\ b &= p_2n + q_2 \\ ab &= (p_1n + q_1)(p_2n + q_2) \\ &= p_1p_2n^2 + (p_1q_2 + p_2q_1)n + q_1q_2 \\ ab \bmod n &= q_1q_2 \bmod n \\ &= ((a \bmod n) \cdot (b \bmod n)) \bmod n \end{align*} \]

이제 곱셈에 대해서도 알게 되었으니 다음 문제를 풀어봅시다.

정수 \( N \,\, (1 \leq N \leq 1,000,000) \)이 주어질 때 \( N! \)을 1e9 + 7로 나눈 나머지를 출력하라.

#include <bits/stdc++.h>

using namespace std;

int main() {
    const int MOD = 1e9 + 7;
    int n;
    cin >> n;

    long long fact[n + 1];
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = (fact[i - 1] * i) % MOD;

    cout << fact[n];
}

여기서도 코드에서 fact[i - 1]과 i가 1e9 + 7을 넘지 않을 것이라는 확신이 있기 때문에 나머지를 구해주지 않았습니다.

이렇게 덧셈, 곱셈에 대한 모듈러 연산을 알아봤습니다. 뺄셈과 나눗셈에 대해서는 알아보지 않았는데, 뺄셈은 어차피 모듈러 연산이 필요가 없고 나눗셈은 어렵기 때문입니다. 나눗셈이 들어간 식에서 모듈러 연산을 처리하려면 모듈러 역원 이라는 것이 필요합니다. 모듈러 역원을 위해서는 다른 이론까지 알아야 할 게 많으니 다른 글에서 다루도록 하겠습니다.