Modular Arithmetic

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

어떤 정수를 2 이상의 정수 \( n \)으로 나눴을 때 나머지는 \( [0, n - 1] \) 범위의 정수 중 하나입니다. 만약 두 정수 \( a, b \)의 \( n \)으로 나눴을 때의 나머지가 \( r \)로 같았다면 \( n \)에 대하여 합동이라고 합니다(congruent modulo n). 종종 문제에서 답이 너무 커지는 경우(예를 들어 팩토리얼), 어떤 수로 나눈 나머지를 대신 구하라고 요구합니다. 여기서 어떤 수는 대부분 1,000,000,007(1e9 + 7)입니다. 저 수는 int 범위에 가까운 소수이기 때문에 널리 사용됩니다. 왜 소수인 것이 중요한지는 나중에 중요한 수학적 특징이 있기 때문입니다.

예를 들어 정수 \( 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];
}

참고로 위 구현은 dp(dynamic programming)이라는 기법이 활용된 풀이입니다. 코드 자체를 이해하긴 어렵지 않으나 dp 자체는 다른 글에서 자세히 살펴볼 예정입니다. 그리고 위 코드는 \( O(N) \)의 시간복잡도를 가지는데 만약 피보나치를 재귀를 사용해서 표현할 경우 \( O(2^N) \)의 시간복잡도를 가지기 때문에 실행이 끝나지 않습니다. 다시 모듈러 연산으로 돌아와서, 위 코드의 문제점은 무엇일까요? n에 100을 입력해 봅시다. 100번째 피보나치 수는 3,736,710,778,780,434,371으로 어마어마하게 큽니다. 200을 넣으면 -1,123,705,814,761,610,347으로 벌써 오버플로우가 발생했습니다. 오버플로우가 생겨서 음수가 되고, 음수끼리 더해서 언더플로우가나서 다시 양수가 되기를 반복하면서 틀린 답을 내게 됩니다. 참고로 파이썬에서는 아무런 문제가 없습니다(!). 파이썬은 숫자의 범위가 사실상 무한대이기 때문에 저런 코드도 문제없이 돌릴 수 있습니다.

참고

굉장히 큰 \( n \)에 대해서 피보나치 수 \( F_n \)은 다음과 같이 근사할 수 있습니다. (Binet's formula)

\[ F_n \approx \frac{\phi^n}{\sqrt 5} \,\,\,\,\,\, \left( \phi = \frac{1 + \sqrt 5}{2} \right) \]

이때 \( F_{1,000,000} \)의 자리수는

\[ \text{Digits of }F_n \approx \left\lfloor \log_{10} \left(\frac{\phi^n}{\sqrt 5} \right) \right\rfloor + 1 = \left\lfloor n\log\phi - \frac{1}{2}\log5 \right\rfloor + 1 = 208,988 \]

대략 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를 구하고 나머지 연산을 하면 이미 정수범위를 벗어난 상태가 되기 때문에 처음부터 범위를 벗어나지 않도록 하는 것이 중요합니다. 여기서 모듈러 연산의 정말 중요한 성질이 활용됩니다.

\[ (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*} \]

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

이 특성은 사실 덧셈보다 곱셈에서 더 중요하게 사용됩니다. 곱셈 특성상 곱하는 순간 32비트 범위를 순식간에 벗어날 수 있기 때문에 주의해야 합니다.

\[ 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을 넘지 않을 것이라는 확신이 있기 때문입니다.

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